Okay - so here it is - an incomplete, imperfect list of two player games that Anita (Mistress of Operations, at Gaming with Chuck headquarters) and I find quite enjoyable. Minor comments are included, ask about any you find interesting in the comments, and there are links to Boardgamegeek listings for these, so you can read reviews, etc.
I purposefully left off any titles that are strictly wargames, although almost all of those are specifically for 2 players. Here is the list - in no particular order. I would have listed Ticket to Ride or Lost Cities first, if I was doing them in order that I would recommend.
Agricola - yes, latin for Farmer. Great game.
Carcassonne - tons of add-ons and variants, the basic game is great
Settlers of Catan - very good. The regular version is only okay for two (I think it is 3 or 4 players, normally) - but there are two versions of card games that are good. The dice game is also awesome, and travels well.
The Rivals for Catan (2 player card game - good)
Catan dice game - huge fun, easy to play, and who doesn't like weird score sheets, and dice with sheep on them?
Tikal - cool exploration game, there is a new version (Tikal II) that supposedly plays faster.
TransAmerica - fun, fast. Play several times in an evening. There is also a Europe (TransEuropa) version.
Lost Cities - best game for couples, ever.
Saint Petersburg - Good. Not as much as some others, but some interesting strategies.
Hansa - great game, and fun. The Author (Michael Schacht) has a great website, with some variants (free to print) available.
Web of Power- from same author as Hansa - I like the medieval version, it is out of print (but free on his website) - but available as "China" - different theme, different board.
Attika - excellent game. Can be a little competitive, but still fun.
Caylus - interesting medieval theme. Collect resources, and place workers, to builds a village around a castle.
Pillars of the Earth - worker placement game (similar to Caylus, above, and Stone Age, below). Lots of references to the Ken Follett novel.
Stone Age - fun worker placement game. All three of these (Caylus, Pillars, and Stone Age) play different enough to each be fun.
El Grande - very strategic. Gives some people a headache to play, but I like it. Not bad with 2 (rules variation) best with 4 or 5.
Terra Nova - fun. Also fun with three players. A little more strategic than some others.
Pandemic - cooperative game. Hard to win. I love it. Anita hates it. Enough said.
Through the Desert - build networks of plastic colored camels. Much more fun than it sounds, and the camels look like pastel candies. Good for 2,3,4 or 5 players.
Ticket to Ride - best intro game to Euro strategy games (all of those listed here). Lots of variants. Either USA or Europe are the best place to start. Nordic Countries is good for 2 players, but so are the others, and Nordic Countries has some weird strategies.
Small World - fun fantasy "wargame" - super light weight, but lots of interesting combinations.
There are others. For instance, I really LOVE Power Grid - but it is a super analytical game (then again, so is El Grande). But I didn't include it because it can be a bit unforgiving. That isn't so much fun in a couples game.