It totally depends on the game.
Team based/squad combat with classes always adds extra spice and variety to online games. Games such as Team Fortress, Tribes1/2, Battlefield 1/2... these are fun since you try to find a need for your team and fill it.
Many MP deathmatch style games are fun- but yes, very mindless. Fragfests can be fun though too! I enjoy Halflife2 DM as it's mindless, silly fun. Older games like Quake/Quake2 had the same kind of mindless fragging.
I do agree though- I tend to prefer a compelling and involving single player game experience. Multiplayer- I usually stick to team based and absolutely LOVE Battlefield2. I'd say if you have a very, very beefy PC- try BF2. It's very fun and involving as there's a lot more to it than just spawning and shooting.