(I posted this on another question about 2-player boardgames which was closed as a duplicate. I appreciate that someone has already suggested Lost Cities to this question, but my answer does go into some extra detail, so I hope you won't begrudge me reposting it here!)
I bought this game for my wife for Valentine's Day and totally got away with it - she loves it!
It's not to be confused with the Lost Cities boardgame - I'm talking about the 2 player card game. Essentially players are archaeologists setting out to discover the Lost Cities of the title. There are 5 different Lost Cities (each of a different colour), and the deck contains cards from 2-10 in each colour, and three multiplier cards. You can play a card to an "expedition" or discard one to a central pile, and then pick one up from the deck or from a central pile; the problem is, once you play a numeric card to an expedition you can no longer play a multiplier, and you can never play a lower number onto a higher one. At the end you total the value of each expedition, subtract 20, and times by the number of multiplier cards plus one (plus there's a bonus for an impressive 8-cards+ expedition).
Obviously you can lose mad points as well as gain them from starting an expedition you can't follow through with! There's a lot of strategy for a simple game, deciding when you can afford to play, when you can afford to discard, and when you just have to cling onto cards for dear life in your hand! A game takes only 5 minutes, and a match is meant to be best of three games. It's got a colourful theme, attractive (oversized) cards, and quite a lot of depth for a game that's so simple to get started with: it's a real couples game in my opinion.
The only thing I don't like about the game is that there's allegedly a 4 player variant - but to play it you're encouraged to buy a second copy of the base game just so you can add it about 20 duplicate cards to your deck. Yeah, right. This fact is not a problem if you just want a game to play as a couple though, thank goodness!