You wouldn't be reading this and I wouldn't be writing this if gaming wasn't an important (or at least enjoyable) part of our lives.  However, I've found that being in a relationship significantly reduces the amount of time I spend playing games; that's not a complaint, just a fact.  I like spending time doing social things and gladly decrease my video game time to do them.  However, there are times when I'd like to game and I often struggle when it comes to sharing this hobby with my girlfriend.

We play games but not often together. We are usually embroiled in single player games simultaneously. 
 
We have played a decent amount of RDR and Borderlands together. Civ IV is another.  

Gaming with my right hand

The only game my wife likes is Little Big Planet.

I've not played many games with with my past girlfriend, but I think you should pick one of the games that isn't something too macho (no Gears of War, sorry) and definitely not competitive - that's only any fun with people on the same skill level. 
To add to your suggestions, I think TBS strategy games are good if she likes tactical thinking, otherwise something creative like Minecraft, Simcity and so on could be quite fun. 
From my personal experience, Rock Band was a lot of fun, so was GTA IV (she liked the look of the game and the city) and Forza 2, just pick a slow car and give her something faster that's easy to handle, it's a lot of fun to crash into each other.

I game with Jill quite often. 

We've mostly played stuff like Rock Band, Guitar Hero, Wii Sports Resort, Mario Kart, Boom Blox Crash Party, and the occasional trivia game like 1 vs. 100.

We play together occasionally but our interests are somewhat different.

My girlfriend enjoys watching me play games if they have a decent story element to them. Other than that I've found that some of the co-op XBLA games are really fun, like Castle Crashers or more recently Plants vs Zombies.

Boom Bloxx is freaking awesome. We play it pretty often.

Adventure games is something we like to play together too. Most recently we played Monkey Island 2. Before that we played Paper Mario, and we are looking forward to spending some time with Costume Quest during our autumn break. 

Try Borderlands, great co op!
 
My last boyfriend was a social gamer too, could play WoW, Guitar Hero or anything like it together, but he wasn't a huge nerd like moi.
Good to read there's still gaming couples out there =)

The lady and I have played the following games, to name a few:
  
Co-op
Halo 1/2/3/ODST/Reach 
Rainbow Six Vegas 1/2 
Gears of War 1/2 
Earth Defence Force 2017 
Monster Hunter Tri 
Monster Hunter Freedom Unite 
DOOM I (XBLA)  
Phantasy Star Universe 
Resident Evil 5 (X360)
Left 4 Dead 1/2 (X360) 
New Super Mario Bros Wii 
Gauntlet Dark Legacy (GC) 
Rock Band 2

Taking in turns/playing alongside each other
Condemned 1/2 
Alan Wake 
I Have No Mouth and I Must Scream (PC)
Viva Piñata 
Call of Duty 2

My boyfriend and I have played  Super Mario Galaxy,  Left 4 Dead 1/2, lots of Borderlands, WoW, and so on - so maybe I'm not the right person to take advice from here.   But I think the Lego games are really good for co-op with a girlfriend who is not a gamer though.  I have gotten a friend of mine to play Lego Star Wars, Indy, and now Harry Potter with me even though she doesn't like games  (she can't even play Mario games because she finds them too stressful).   I agree that Little Big Planet could also be a fun co-op game to try.  Also puzzle/adventure games like Machinarium or Tales of Monkey Island could be good too.
 
Also, I want to say that while you shouldn't spring a "hardcore" or "macho" game on a new girlfriend without warning, you also shouldn't be afraid to maybe slowly introduce that kind of game to her.... maybe show her Fallout or Ratchet and Clank and how cool and fun that  can be... that could be a gateway drug!  Girls can like all kinds of games too!  I think some girls who don't play games just don't understand sitting in front of TV/computer for hours playing a game, they think you're ignoring them, so anything where you can try to involve your significant other in your game time is always great!

My girlfriend and I played through Heavy Rain and she loved it. I manned the controls and she had to quickly say the decisions she wanted the character to make. It was actually pretty fun, especially the times where she was so immersed in the game she forgot to give me a command, so the character would do nothing in high pressure situations.

I haven't played anything with my wife recently. Not since the drunken Dungeon Siege 2 incident. >_> 
 
But I keep a list of games to possibly play together in the future. Yes, my nickname for her is Dragon.

I don't know, you might be doing her a disservice by sticking to traditional "girl games" like Rock Band and the Lego series. I played Rock Band 2 and Lego Star Wars/Indiana Jones with my girlfriend before anything else, and she wasn't too keen on either. She LOVES playing Resident Evil 5 and Left 4 Dead though, and has been getting into playing Reach with me recently too. She isn't one to play online versus type stuff, but that will probably come with time.
 
It won't be the same for any two people and this was just my experience, but give her a chance with some solid co-op games as other people have said and don't think right off the bat that any game is "too hardcore."
 
Personal recommendation: Resident Evil 5. Some of the best co-op I have ever played, and my girlfriend agrees.

Burnout Paradise, Borderlands, Viva Pinata 2, Plants vs Zombies (XBLA), Pixeljunk Monsters, LittleBigPlanet. 
 
That's off the top of my head. Borderlands is the big one at the moment.

My gal and I enjoy Carcassonne, she is ruthless at that game. She mostly likes puzzle or strategy games, but will occasionally want to play games like Halo, Left for Dead, or Gears of War. Like others have said here, co-op is where it's at.

My last ex was the only one of my girlfriends that played games. She mostly played JRPGs and I stay away from those. Although she did have fun watching me play Portal, and we played Halo 3 campaign together. I hope the next girl in my life is a gamer too.

Resident Evil 5 was tons of fun to play with a girlfriend -- similar co-op focused games like Gears of War worked really well for me, too. Asymmetrical co-op sometimes worked, so long as the game was really good. My last girlfriend loved collecting star bits and poking Lumas in the Mario Galaxy games. Games like Persona 4 were popular too; I think watching and having a role in advancing all the different romantic and platonic relationships in the game had a lot to do with that. 
 
The good news is that once you find a game or two she really enjoys, the easier it becomes to expand upon those tastes.

 When it comes to games to play together  (besides the obvious music games), the big ones for me and my husband are MMOs or RPGs .  We do some occasional shooter, but I have to really be in the mood for it, and he knows it.  Many, many hours have been spent together over TCP/IP in games like Diablo 1/2 and Sacred 1/2.  Console games like Borderlands are great too.  Sometimes we'll even take some single player game, like a tower defense game, or Puzzle Quest, and watch each other play and give each other tips.  
 
The big question is this though:   On her own, what types of games does she prefer? 

I can probably play anything with her, but she has a bit of trouble with FPS controls since she doesn't really play them. 
 
Co-op is really the best because one of us tends to get kind of bitchy when losing streaks happen (tends to be me, I'll admit) and she doesn't like being helped when she's doing single player and I'm helping her. She also gets bored of watching me play. 
 
On that note, she also has a lot of games that she plays, like Plants vs. Zombies and Sacrifice. There's a few more but I can't think of them.

My fiance and I tend to play single player games even together... he'll come and sit with me while I play through Fallout, etc. Other than that we play Borderlands, Halo, Rock Band, LBP, COD, Resi 5, Lego games, Lara Croft, WoW, Left 4 Dead... all sorts really.

what is this significant other you speak of? Is it some sort of alien life form that  holds ancient artifacts which lead to the knowledge of the secrets of the Universe? 

My girlfriend had no experience with gaming at all when i met her, but during the last 3 years we've been together she has learned to play games with me, or even by herself.. 
The tough part for me is finding games she like.. as you said: simpler is better.. shooters are not the first game most new gamers will want to play.. especially girls (not trying to be sexist here :)  
I, myself is 23 years old and my girlfriend is 21, giving you a sense of things.. 
 

here are some games i can recommend for the both of you to play together:  
The LEGO games (as you mentioned) 
music games like Rock band, DJ Hero, Guitar Hero, Singstar/Lips 
Quiz games like Buzz/Scene It 
Castle crashers (my girlfriend loved it, as did i..)
Limbo (taking turns)(The artstyle amazed my girlfriend) 
some puzzle games.. (keep it simple, don't start out with Puzzle Quest ;) ) 
Fighting games where you can team up against the AI (like Tekken Tag Tournament) 
Depending on your significant others' taste, kids games can be a great choice. a game like UP that is simple and colorful can be very entertaining. 
 
 
My girlfriend also likes to play some games by herself.. it really helps her to develop a taste for gaming and can help me figure out what she likes.. 
 some of them are: 
 
The sims 3 (if your girlfriend has just a small interest in decorating your house/apartment she can go balls the in all the customisable stuff in this game) 
Kung Fu Panda (platforming and simple fighting seems to be a winner) 
Everyday Genius: Squarelogic (a Sudoku type puzzlegame, easy to play, and makes you think that you're smart.. ;) 
 
 
On a last note, try showing her something with a great story.. my girlfriend can watch me play a game for hours if the story sucks her in.. like watching a great movie.. horror games MIGHT work too.. 
 
Sorry for making this such a long post guys.. don't know what the hell happened.. :S

rockband is the only game I'll play with other people

" However, I've found that being in a relationship significantly reduces the amount of time I spend playing games; that's not a complaint, just a fact.  I like spending time doing social things and gladly decrease my video game time to do them.  However, there are times when I'd like to game and I often struggle when it comes to sharing this hobby with my girlfriend. "  

super smash brawl. 
 
whoever loses gets to suck/lick/blow the other one. win win

My girlfriend will only ever play Quackshot, Puzzle Bobble or Wii Bowling.  It's so annoying.  We did manage to get through Broken Sword The Zleepin' Dragon but that's it.

My girlfriend is a fan of RockBand and Guitar Hero.  She also loves Wolfenstein 3D and BurgerTime for some odd reason as well.

I tried to teach my last girlfriend to play Fallout 3. Pure disaster. 
 
And the last girl I was seriously talking to calls Starcraft 2 "that game with the things that make weird noises when I'm trying to sleep". 
 
I obviously play as Zerg.

We usually play stuff like Rock Ban or Carcasonne.

Heavy Rain is fun when taking turns in between each character.

Me and my girl love to play  
Burnout Paradise 
Army of two the 40th day  
Borderlands 
Pretty much any co-op game or racing game like NFS or burnout.

I met my guy on an MMO.. so ya we play games together :)
We've played about a dozen MMO's together (me cleric & him warrior)
Lots of Co-op games (Borderlands, Resident Evil, Left 4 Dead, CoD for example)
 
Ours is a long story, but a good one :)

fable II was instrumental in getting my wife more into gaming. Springing off of that I got her hooked on dragon age. occasionally we play sacred 2, and while we have marvel ultimate alliance as well, we haven't gotten around to it (it was 7 bucks, so w/e). we'd have more to do, but she struggles with FP perspective, which unfortunately cuts our choices down substantially. still tho, co-op play with the wife is 1 of the greatest experiences ever!

I know it's cliche, but I bought a Wii and it's been a huge success. She loves Wii Sports Resort, Wii Music, and Samba de Amigo. I guess there is a reason Nintendo now absolutely dominates the casual market. Next up, I'll be looking into the Kinect.

I was lucky enough to find a great girl who grew up loving games just like I did. Her tastes are a bit different, of course, but we've found quite a few we both like. She usually likes 'cute' games, with a pleasing art style. Simultaneous co-op is a must, and the last two Kirby games (Epic Yarn and Return to Dreamland) have hit the mark. New Super Mario Bros Wii was good, but a little too difficult. The girlfriend and I have played through all the Lego games (except Harry Potter); those are some of our favorites. I'm thinking the next game we get might be the new Rayman game, the co-op on there sounds pretty great.

Anyone reading have other 'cute', simultaneous co-op games they would recommend? A lot of the recs in this discussion don't really fit my girlfriend's tastes.

Old Republic

She's the one I keep /hugging.

Only Lego and Resident Evil 5