I've got one for you! It has single-computer co-op and a network mode I never tried. And it isn't an FPS!
I heartily endorse Little Fighter 2:
http://www.lf2.net/Ever play River City Ransom? Or maybe something vaguely close like Golden Axe? It's a beat'em'up with a fairly extensive cast of characters with special attacks and attributes that ranges from normal difficulty to face poundingly insane. It has a few special modes, that I'm not sure work over Network; a huge Army mode with hundreds of people fighting at once, and so on.
Best of all? Moddable. Characters are moddable particularly. The stock ones are varied-- you have a lot of bare-hand brawlers with ki-like attacks, a couple armed characters (one with very useful armor!) One fellow with a bow and arrow, a ninja, and my favorites; an ice mage and a fire mage. And the unlockable boss characters...
The game has a lot of neat traits. For instance, a particularly awesome co-op experience. If the fire mage and ice mage are on the same team and both are at 25 percent health or less, and they decide to run into each other and tap the directional key, they'll fuse together and become the incredibly powerful Firzen. He creates flaming ice explosions, huge energy waves, and can generally melt faces. It wears off though, and you'll be in worse health than before.
The campaign mode is pretty long but mostly just rooms of enemies. You can play with up to eight characters-- any number of which are AI controlled.
Besides that, the co-op-ability is pretty good. Some characters heal, some support well, one can create an item (an ice sword, actually.) All of them can help each other break out of enemy combos and take hits for one another.
Best of all, it was just updated to 2.0. Looks fancy and awesome again.
Hm, I should create a thread here about it, I never did get to try Network and who better to play with than Bay 12 forum goers?
Edit: Screenie.
Bad shot, because it's hard to see what's going on. 4+ players is the most fun, because things are simply insane. Version 2.0 is nice-- it has an optional Toolbar installation to support them, and a few minimal advertisements on the titlescreen, but it's a freeware game. (Is it still freeware if they sell the titlescreen for adspace?)