Race For the Galaxy is fantastic, easier to learn than it looks and deep.
Ghost Stories is also great and is co-op which helps sell it to my wife.
ETA: I wish my wife would play Roborally, I love that game, but most people I’ve met can’t handle visualizing the order cards.
Just kickin it old school -
How about Backgammon and Chess? They don’t have to be serious, quiet games! They can be quite fun if you approach them in the right way.
Try this link: http://www.boardgamegeek.com/geeklist/16912/just-us-two-a-couple-close-gamers-weigh-in-our
I haven’t seen anyone recommend Lords of Waterdeep yet, which I quite like with two players. It goes up to five (six with new expansion), although five players is sort of crowded.
If you do decide to get Agricola, rather than trying to decode the rulebook, I recommend watching a video of basic play. Board Games with Scott is good, but I’m sure there are others.
Another option for Agricola is to pick up the 2 player variant Agricola: All Creatures Big and Small. It is lot easier to learn and more forgiving then its predecessor, but still has interesting choices throughout.
In just the first minute I learned I’ve been pronouncing the name wrong.
Yeah, it’s not a farmers’ soft drink.