Worth mentioning, in this context, that Carcasonne: Hunters and Gatherers is a significantly better two player game than the basic Carcasonne system. If you weren’t playing H&G, I’d suggest giving it a chance if you get the opportunity. I don’t like base Carcasonne, but H&G adds just enough additional elements to the base game to make it fairly enjoyable and strategic.
Lost Cities is a great spouse game - it is one of the very few games that my non-gamer wife actually enjoys playing. Simple, yet satisfying. Get it.
Caesar and Cleopatra and Hera and Zeus are designed as spouse games; both are playable.
Guillotine is a fun game, but I’d never play it again with 2 players. It needs several players for it to be worthwhile playing.
A couple of suggestions that I haven’t seen anyone else mention yet:
Reiner Knizia’s Battle Line. A variant on the Lost Cities gameplay (a little more complex and random) and based around ancient warfare.
Reiner Knizia’s Lord of the Rings. Definitely not a game to everyone’s taste, but I like it. As a spouse game it has two definite advantages: it’s simple and it’s cooperative. Being Knizia, it is also surprisingly deep given the simplicity of its rules and it’s one of the few Knizia games where the theme actually feels right, IMO.
The Lords of the Rings: The Confronation may also be interesting, being specifically 2 player, but I haven’t played it.
Blue Moon City. Another Knizia (hmm). It has a very weird theme - fantasy races are rebuilding their capital city after a civil war - but the game itself is just a fantastic strategic area control and resource management racing game. The modular board makes it highly replayable, and it plays 2-4 players in about 60 minutes. It’s really a pity the theme is so obscure, because this is without a doubt the best family game in my collection.
Just to round out the Knizia-ton, one might as well mention Blue Moon. It is a two-player battle game (which “precedes” Blue Moon City). Haven’t played it, but the game does have its fans.