Borderlands 2 supports four-player co-op, and offers five very different playable classes. It's a blast.
I haven't tried it, but SOCOM 4 supports five-player co-op.
For two players, I'd recommend Resistance 3.
Metal Gear Solid: Peace Walker (available as part of the Metal Gear Solid HD Collection) supports four-player co-op through its entire campaign; a lot of stealth, mixed with boss battles.
Red Dead Redemption's biggest strength is its single-player storyline, but it also offers some multiplayer modes.