Diplomacy is a wonderful game, but it does have the initial random chance draw for countries, which are **not **equal, e.g.:
Also it’s not like chess (apart from needing concentration).
You usually can’t predict more than one move ahead in Diplomacy. The game requires knowledge of emotion and who you can trust. The threat of backstabbing is always present, but too many backstabs mean you can’t form alliances.
Another two-person game you might enjoy is Odin’s Ravens. It’s got many of the mechanics of a good “German” board game: deft combination of random chance with strategy, ability to affect the opposing player, cool little wooden pieces and artistic cards/gameboard. And it plays fairly quickly, which means you can get a lot of results in a short period of time, allowing you to try different strategies and get some idea of their effectiveness without spending a month of Sundays doing it. 
I didn’t mention Pandemic because I saw it for the first time on Saturday.
The fact that it’s a cooperative game instead of a confrontational game makes for a very different style of play.
I have been getting a lot of use out of my copy of Dominion of late. It is a deck building game in which you use your existing deck resources to purchase additional cards to add to your deck. There are multiple strategic paths to victory, and the game plays well with two, three, or four players (the strategies change with the number of players). Further, the strategies from game to game change since you only play with a subset of the available cards in any given game, leading to quite a bit of replayability. It takes a few plays to get the hang of minimizing downtime, since there is a lot of deck shuffling. After awhile, you learn how to time your deck shuffling and other non-interactive tasks while others are taking their turns.
BrettspielWelt is a good place to test drive games. It is a free site that features online play for some of the more popular games. The interface is somewhat confusing at first, though.
I originally came here to recommend Order of the Stick, but then I thought about it; my friends and I like the game because we like the comic strip, but each time we play it tends to end up a very long, drawn-out process, and we rarely actually finish a game (the small version of the game takes several hours at least). Therefore, I recomend, as a non-board game, Grave Robbers from Outer Space, Kung Fu Samurai on Giant Robot Island, and the various others in the ‘series’ (Link: http://www.zmangames.com/ and scroll down to the ‘b-movie releases’). Won’t run a whole night, but they’re very, very amusing ‘quick’ games.
Boardgamegeek.com is my mecca, and their advice is sound.
Ticket To Ride - A telltale indication of a good game is the amount of expansion/spin offs it generates and this is true of* Ticket to Ride*. The rules can be explained and fully understood in minutes and the dynamic complexity becomes obvious almost as fast (ala Settlers of Catan). It’s needs anywhere from 3 to 5 players, 3 kinda sucks but 4 is good. Luck isn’t as much of a factor and planning and staying ahead of your opponents reveals a true savay player. Ticket to Ride is a game where your 10 year old could beat you and deserve the win.
Fury of Dracula - up to 4 players try to hunt down 1 player as Dracula running and hiding in Europe, the map and components are beautiful and tension builds for everyone as the trail gets hotter. The designers have really struck a great balance between the two sides and my friends as I are approaching a 50 - 50 split in wins
Bohnanza - I really don’t care for card games, but I must admit Bohnanza is flat out addictive. An auction game, each of the players tries to grow the most beans in their fields to turn the highest profit. My girlfriends family was in to this and I picked it up fairly quickly.
Mag-blast - Is also worth a look, each person is a different race and you all fight in direct combat in space. The game is funny and has a fair amount of strategy that can overcome luck. It does suffer a bit from the ruthless picking-on-the-weak-guy tendencies of games like Risk.
Among games I haven’t yet played, but will soon get:
*Agricola
Puerto Rico
San Juan
*
2 player games I have played and love:
Twilight Struggle
Balloon Cup
Pick & Pack
Lost Cities
I forgot to add Evo to the list before, a game where you strive to evolve your dinosaurs to be as successful as possible before the comet comes. A bit strategy board game a bit auction for the genetic advances, the best part is when you decide what mutations will help the most and what you can afford to outbid your opponents by.
Geeklist that matches # players to the game (in light, medium, and heavy categories)
Brian
Most of the recommendations I thought of were already mentioned – a couple others you might want to check out are Thurn & Taxis (a route-building game but with very different mechanics from Ticket to Ride – the routes are means toward the end of setting up station houses, and players race to achieve goals first but don’t directly “block” each other) – and Cartagena (a race game with quite a bit more strategy than you’d expect from its simple mechanics; plays in about 20 minutes).