I easily second: Diablo 1/2, Baldur’s Gate: Dark Alliance 2, Champions Of Norrath when it comes to action RPGs, and Serious Sam when it comes to FPSs.
I love Dynasty Warriors/Samurai Warriors, but its co-op mode only magnifies the already annoying slowdown/pop-up problem you see in singleplayer. I’d go with The Two Towers instead for old-school beatemup action. I honestly think it’s as good a pure game as any DW/SW title, it’s better than RotK by a small margin, and the co-op just makes it all the more kickass.
Here’s an idea: maybe sports games? Oddly enough, I don’t know if my two favorites, Sega NHL and NBA Live 2004, offer co-op or not, because my friends and I have been too busy competing against each other to ever bother trying to play on the same team. I’ll look into the possibility, though, because assuming it’s possible, those two games in particular are simply outstanding. You’d have to harbor an avid hatred of hockey and basketball to not enjoy them. As far as complexity for noob players goes… Sega NHL lets you play with simplified controls in case the anyone finds all the advanced options to be too intimidating. Same with NBA Live, but I can’t imagine anyone really being overwhelmed by its “Freestyle” controls. If you do play with simple controls in either game, turn down the difficulty because you will lose the ability to pull off some funky moves that are very useful, and the AI will not take pity on you.
Fighting games tend to not include a co-op mode - well, maybe Tekken Tag does but I thought that game was totally average and forgettable. The closest you can probably get to a co-op “fighting game” is actually a series of wrestling titles. The two latest WWE Smackdown! games support up to six players, and it’s easy to set it up so that you and a friend can tag-team up against the AI, or another tag-team of two friends, or whatever. And unless you hold pro wrestling in utter contempt and cannot imagine yourself possibly enjoying games based on it (believe me, I can understand why for a number of reasons, although personally I find it enjoyable in the same way I find Roger Corman movies great), you should have an absolute blast with Smackdown. They have the best “create your own character” mode I’ve seen in any game, period - you can lose yourself for hours just screwing around with that and not playing the actual game.
I can’t remember if Ikaruga has a co-op mode or not. If so, it might be worth checking out. It isn’t my favorite old-school shooter ever, but it’s fun enough, ya know? I can’t think of another recent old-school shooter that offers co-op, but I’ve only paid a small amount of attention to this genre. All the awesome little freeware PC games I have - none have co-op. =(