I'm looking for a game for me and my girlfriend to play together online. The catch is that shes pretty new to gaming, so anything too complicated or twitchy might not work. Also, I don't want anything too violent or bloody, just a nice game for us to play together when we have some free time. Any ideas?

I'm not really looking for an mmorpg. I'd prefer something that we could play alone, without other human players. Some good suggestions so far.
BTW, how is HoMM 5 different from the first four? Its the only one i haven't played.

Better than HoMM 4 and in my opinion about on par with 3 (which for me is the best), maybe a bit lower. Think of it as returning to the original formula after HoMM 4 strayed from the path :)

Are console games an option? Lego Star Wars might be good, its a fun reasonably gentle game with the added bonus of being 2 players on the same system which can be more fun than playing online

Manhunt.
I mean, uh Peggle. Yeah. Or if you want something educational, Plants vs Zombies.

Guys, take note that he wanted online multiplayer which means they won't be in the same room, heck, maybe not even in the same region.
It's extremely easy to recommend single player games like Plants vs Zombies or The Misadventures of P.B. blahblah or Machinarium or a lot of good games, but they're not multiplayer games ;)

Ahh well I wasn't sure about the distances involved. If she doesn't have a 360, it might not be a bad investment since the arcade is fairly cheap, you could play games and it functions damned well as a VOIP box which might be a good saving on phone calls.
Of course live gold is a bit of a rip but you can get 12 month codes on ebay realatively cheap (way more so than in the shops anyway)

Does Trackmania fit? It's a free arcade racer and (I think) it has multiplayer...

Does it really have to be online ? Online non-MMO games are usually highly competitive and those with co-op are likely pretty violent...
If she really is new to gaming, I strongly suggest casual single-player games. It can be fun for both of you, if done right, although you'll have to be very patient and subtle... but in return you'll spend quite a while bonding and she'll get into computer games.
A good start would be giving her something like The Longest Journey or Monkey Island so that you can sit next to her and listen to her thoughts on characters, the plot, the meaning of life AND offer subtle hints if she gets stuck ;).
Also - you definitely have to get her Zuma ;P.
Let's hope that's not the case...

Diablo II + expansion, if that is not too violent. I am not sure if killing monsters is a 'bad' thing, but I have no idea about her violence threshold; it isn't as if there is excessive blood spatter or anything. The game itself is not too hard to learn (point and click), and there is the tangible reward of leveling up and getting new equipment. It is pretty much designed for small group co-op, so there is that as well. Amazon sells both the game and the expansion for around $13 (each).
I am having a hard time thinking of anything else that might fit your criteria (I generally play single player offline games). I would probably keep her away from MMO type games, honestly. If she gets into it, you may never see her again. That MMO thing is like crack for certain personality types.

Yes, actually that is the case. I'm starting to think a turn-based strategy game might be a good idea. Anyone know any that are relatively simple and straightforward? (HoMM is already on my maybe list, I wish we could play Civ4 though I'm worried that its too complicated)

Bah, ninja'd by the OP, refuting everything I said! Well, almost everything. Sins of a Solar Empire is my vote, if you are intent on a strategy type game.. It isn't a turn-based strategy game, but that may not be a bad thing. It is actually slow, by real-time strategy standards, and it wasn't too complex as I recall.
The trouble I had when I played Master of Orion 2 with an old GF (over a decade ago, yeesh), was that it get tedious towards the end. Even playing with concurrent turns, someone always had to micromanage (new technology that turn or whatever), and the other person would have to wait for the turn to end. Usually I would end up surrendering to her, and then just watching her finish out the game.
I'll look for a TBS game that is simple that doesn't require a lot of micromanagement . One must exist somewhere, but I don't think I ever played anything like that.
EDIT:
Yeah, on second thought you might be right, the HOMM games are not THAT bad with micromanagement. At least not as bad as some games i have played. I would just buy one of them from here and see how she likes it. They are not that expensive, after all.
I still think sins of a Solar Empire (for strategy game) or Diablo II (for a co-op type game) would be better, but to each his own :).

Trackmania Nation's multiplayer is hot seat. One player makes a run, the other tries to top it on his turn. When you're racing, you can see a "ghost" car repeating the best run of your opponent and know this way if you're winning of not. It's actually entertaining to play it that way, specially between two players. Too many players leaves a lot of people standing around doing nothing.

I second what AndrewC says. The universe in single-player HoMM 5 is a bit more self-contained, too - the plot makes a bit more sense if you aren't familiar with other M&M or HoMM games.
The switch to 3D makes the battles seem a bit more exciting, too.

Right now I'm playing the Baldur's Gate series with my girlfriend, which is fun, if you get the multiplayer to work. Something like Neverwinter Nights might work as well, depending on your tastes.

Every girl I know IRL plays Sim 2.
Generally girls I met in the internet played Prince of Persia: Sands of Time, Max Payne, Mass Effect and Mcgee's Alice.
Girls prefer the Prince.Especially when he starts to strip.