All the Half Life games
COD: MW2
Costume Quest
DNF
Dungeons of Dreadmore
Lego Batman
Rest Orchestra 2
Sacred 2
Recettear/Chantelise
Theatre of War
Tropico 4
Preferably something that isn't too complex, has a decent single player to get me started, and good multiplayer.
Also, would be nice if its not something where everyone is going to soulcrush me. I enjoy playing RTSes, but I'm pretty terrible at them.
Honestly, I'd say starcraft 2. It can be a little intimidating, but the single player is 28 missions and reasonably good fun w/ lots of replayability/achievements/difficulty modes, and the multiplayer while daunting at first tries to give you a 50% winrate by skill level matching and does a good job of it - the only people who truly "break" that are either the bottom 5% or the top 5%.
+1 on SC2 even if you'd never play the multiplayer the singleplayer is already worth it. It's pretty fun.
Multiplayer obviously epic and like dlorc said ladder system balances.