I’m gonna 2nd Stratego and mention Mastermind. Both have a short learing curve, but take years to master. Ok, Mastermind don’t take years to master, but it can be a lot of fun in small dosses.
dead0man
Mancala. Simple rules, lots of depth.
There’s a card game called Lost Cities which has a strange fascination. Try Funagain Games on the Web; I think they stock it.
Played tons of Cribbage with my old college girlfriend, who stomped by fanny regularly.
If you’d like a boardgame with a light war theme, Battle Cry is a lot of fun; Wizards of the Coast has apparently got it on sale just now for $20 or so. Heckuva value. It’s a light simulation of Civil War combat, with lots of different scenarios.
There are lots of good suggestions here, but not all are real good for 2 people-- mostly I’m thinking Trivia games kinda suck for just one couple.
I like chess, backgammon, Mille Bornes, cribbage, etc… for 2. Knightmare Chess is a great addition to any chess set.
Just make sure your SO also likes playing games…
A great new board game is Kings Cribbage (official site). If you like Cribbage, you may like Kings Cribbage (review) even more. I know I do.
I’m not sure if I’m allowed to plug like this, but Rocketeer already mentioned them: Funagain Games (I don’t work for them, I just love their website) Search for 2 player games. Read the reviews.
And some recommendations:
Carcassone (beautiful, and fun. Highly recommended.)
Samurai (NOT samurai swords, just Samurai, by Reiner Knizia)
Guilliotine (card game, but fun)
Set (another card game)
Ceasar & Cleopatra (another card game)
Zertz
I know this may be a bit weird, but have you tried Magic: The Gathering? (don’t get sucked in, just buy a deck or two for each of you.) May not be to your taste, though.
And seconds to:
Lost Cities
Knightmare Chess
Cathedral
If you try Heroquest and like it, and if you happen to be a fan of Buffy the Vampie Slayer, you might want to try the buffy board game. It has been on sale at Toys R Us for months at $4.97, and believe it or not, it’s not a bad game at all, in the heroquest genre.
Go 
Some interesting ones are: Axis and Allies, Illuminati (best with 3 or 4 players), Dungeon (a very old TSR game).
Ricochet Robots is a great logical/spatial puzzling game to play when you’d like to do something together, but also don’t feel much like chatting–games of it tend to be spent in intense concentrating silence. Sort of a niche market, but great fun if you’re in it.
Minion Hunter is an unusual thing–rather than competing against the other player(s), you work together to try to overcome the rules you’re up against.
We play:
Othello (fun!) along with Scrabble (much fun) Backgammon, Uno, House-Rules Monopoly. We liked Stratego (sp?) but the housemate with the board moved out. Sometime we play drinking Jenga (can be very frustrating and noisy) Operation can be fun…but usually only for a little while.
You guys will have a lot of fun playing games together. 
You could try Mah Jong or, if you want another card game, there’s Canasta.
But for interaction as mentioned in the OP, I would have to go with the earlier suggestion of Twister. 
Now wait a minute, Mah Jong is usually for four people. Maybe you could have some friends over to play that and Twister.
Good call, Drastic, I was wracking my brain for something that was on the tip of my tongue. It was in fact Richochet Robot. Great game, but you have to be in the right mood. (The “ow, my brain hurts” mood to be exact.)
I haven’t heard of Minion Hunter, but another cooperative game that’s all the rage right now is the new(ish) Lord of the Rings Board Game (also by Reiner Knizia, my favorite game designer).
two players, relatively simple rules (not as easy as checkers, not as complex as chess) and a game can be knocked off quick unless you or your partner like to endlessly ponder your options. (of course, a timed game takes care of that).
I loved this game to death until my wife started to routinely beat me at it
I’m gonna try me some of these other games. Sounds like fun! (I also tripped across a website last week that specializes in a lot of the building sets I wanted when I was a wee 'vark: erector, technics lego, k’nex… All I need to do is wait for my daughter to get old enough and convince her that mechie stuff is kewl…)
'vark
Not necessarily a game, but some good laughs could come from y’all playing with Mad Libs.
If you like thinking games I vote for Go. The rules are pretty simple but the game is at least as hard as chess and probably harder. (There is a huge debate about which game is more complicated) It is elegant and fun though the learning the game takes a while.
A good place to start it http://panda-igs.joyjoy.net/English/sintro1.html
Slee