I'd put a vote in for wow definitely.
Trying to think of what my gf and I play together a lot...
League of Legends? its free, and if you play against computers at least to start you can kind of learn at your own pace.
We love playing rise of nations together...be the same nation and have one person do economy and the other do military.
Diablo 2 definitely
How about an old school game on an emulator? We love playing Secret of Mana (on an actual SNES baby) and streets of rage remake.
Along the wow lines is Lord of the rings online if you don't want to pay monthly, quick to get into if you want.
How about Lego star wars and some of those other games? Despite sounding like little kid games, theyre tons of fun.
id head over to
http://www.co-optimus.com/ and check out some of their co-op games.