Sports games... pick any field.
Starcraft... WOW... (you may never see each other again)
Final Fantasy (think that made it to PC)
RPGs.... puzzle games...
If she's not against blood and guts, Left 4 Dead.
Frankly, I'd say take her out to a game store. Make it into a trip
for the both of you, browse what's available. Check for co-op on the back.
Try and find something that's not just an co-op, but can be seen as an achievement for
both of you together.
That will be infinitely better than just getting some game and saying you'll both play it.
This isn't like buying a lawn mower, or some jeans... think of it as a personal quest.
One of the best pieces of advice is to never stop dating, even after being married.
If you like the price online better, then just browse and then buy online.
The Wii honestly I've first hand seen gets a lot of attention from the female audience both young and old.
Mario Kart, Mario Party, some of the puzzle games there would be what I'd really suggest.
XBLA also has some stuff, but that's even more cash down the tubes.