Zork

If she doesn't mind watching, play a horror game that can scare her (but not too badly) and one that you are good at beating. With all the adrenaline from the game, both of you will have a good time.

If not, play a game she is good at or something you think she will be good at.

World of Warcraft. It's the best game for couples.

came here to say this.... she will think she is waching a movie.

As an opener, Mario cart, world, galaxy, LBP if you're wiiless.
Then Portal 2, uncharted 2, something for a story if you want that angle

This is a really interesting question. Lately I've been playing a lot of games in the same space as my wife, and I've learned a few things.

Unsurprisingly, cinematic games can be enjoyed by bystanders. Uncharted 2, for example, was a big hit. It doesn't hurt having a globe-trotting Indiana Jones-esque storyline and some well developed female characters either.

Bastion, conversely, was a swing and a miss. Although I enjoyed playing it, she was bored to tears. It might have been the isometric view, or the cryptic storyline, or maybe the repetitive action, but it didn't work.

Darksiders was actually her favorite. The story was interesting to her; the crumbling, post-apocalyptic world was engaging; and she experienced the challenge of the game vicariously through me.

So this is my theory: go with a third-person action or action-adventure game with a good story, good art direction, and good music.

Final Fantasy X-2....

...

Generally, WRPG adventures, so Skyrim etc or fighting games would be my choice, fighting games because she can join in.

Personally, if she doesn't like gaming and is new in your life, I would pick something else to do.  That being said all girls seem to like Katamari games.  If she likes sports, a sports game would be a good choice too.

Well, Kotawa Shoujo of course

Racing. Or movie quality.