First thing I'd ask is : do you/your gf enjoy abstract games (as in Chess, Go etc) ? If so, I would recommend the GIPF project, specifically YINSH and DVONN, which are "modern" abstract two-player strategy games.
Other than that, I have three 2-player games that I really like right now, but there's a bunch of them :
- Mr. Jack. This is not an abstract, but it can sometimes feel like it. There's a board wich represents the streets of London, with 8 characters on them. One player plays Jack the Ripper, and is randomly assigned one of the characters on the board. The other plays an investigator and has to cath Jack in a certain number of turns. It's a deduction game in which the primary mechanism is that there are sources of light on the board (street lamps), and as Jack you indicate each turn if you're near the light or not. Each player moves half the characters each turn, and they each have powers which make the game really sound strategically but not too easy to predict, which avoid trying to think 15 turns ahead, i.e AP. It plays in half an hour.
- Seasons. This is not exclusively 2-player, theoretically playable up to 4 players (although I wouldn't recommend it, 3 players is fine though). It's a card game with wacky/cute theme and illustrations that a lot of people seem to like (I don't so much). First you each draft 9 cards, and then you divise those cards in 3 groups of 3. The game is played in 3 "years", so the cards are assigned to each year. Each year is divided into four seasons which each have a custom set of dice. Each turn you roll 3 dice, and each player selects one. Those dices will essentialy get you energy of a specific type (cards cost energy, kind of like mana costs in Magic). Basically the idea is to find powerful combinations, which should apeal to Dominion players. Also, the game has very good recommendations for the first few games (no drafting, some cards excluded) which allow it to be fairly complex but have a good learning curve.
- Targui. I have only played this twice so I don't know how much replayability it has (the previous two have a bunch of that, not sure with this one), but it is a good strategy game where there's a grid of actions, and a whole system of getting extra actions based on where your actions line up (can't really explain this well, you'd have to look on BGG I think). It's a pretty good, classic euro-style 2-player game.