Duel of Ages is fun. It’s about halfway between a board game and a role-playing game. I’ve only played the basic version myself but there’s several expansions.
The Duel of Ages website.
Arkham Horror has been re-released. It’s a very fun boardgame; Lovecraftian knowledge is not required but can add to the fun. I have the original version, and I’m thinking of getting the updated one.
I’d suggest Talisman, but it’s been out of print for years and will never be re-released. You can get it on eBay, but the prices are very high.
Robo Rally is fantastic fun. You should definitely grab it when it comes out again.
Owning a toy store, I have a little bit of experience with games. My favorite is an old pub game called Shut the Box. I carry this one by Front Porch Classics. There is a $25 and a $50 coffee table version. I, personally, cannot stop playing it!
Also, this is a newer game that has won a TON of awards that I sell a lot of: Wordigo.
Finally, my other favorite and best seller is Blokus.
BTW, all of these links go straight to the manufacturer’s websites. I will not profit from any purchases you make. 
It’s Rummikub, actually. And as you might guess from the name it is identical to the card game Gin-Rummy.
To the OP: others have mentioned Puerto Rico but that is not a 2 player game. If you like Settlers, I wouldn’t bother with the Seafarers expansion but Knight and Cities is OK for a change. Better still is an entirely new take on the system called Settlers of the Stone Age, which I now prefer to the original Settlers.
The best rail game IMO is still Rail Baron, but again that’s not two player. BTW there is a wickedly good computerisation of it available at Rail Baron® Fanatics - it also has several alternate maps available some of which are very good.
I’ll second RoboRally, but you need to not mind having to do a bit of spatial thinking.
Most of the games by Cheapass Games are worthwhile, and it’s hard to beat the price – they sell you the rules and board, but not the pieces or fancy packaging. I personally recommend Kill Dr. Lucky and Totally Renamed Spy Game.
Are you pondering what I’m pondering? Where are the board games of my youth? We need the classic’s here, Monopoly as previously mentioned, Scrabble and my all time favorite Risk. Hell, checkers and chess are board games too.
Here are some suggestions. I am a German style boardgaming fan.
Classic:
Settlers of Catan - Excellent game for 3-4 players. The base game is a ton of fun with alot of replay value.
Euphrates & Tigris - This is a real brain burner. I haven’t played in a while but I do enjoy it.
Strategy based:
Medici - I played this recently and loved the bidding in it. You bid your points for cargo that then scores more points for you. Theme is weak, but game is good.
Alhambra - Very enjoyable tile laying/buying game. A bit on the luck side I think.
St. Petersburg - I like this one alot if could fit in the light/easy category once you learn it.
Struggle of Empires - New to our group, we have played a few times, this is a longer game, 2-4 hours depending on number of players. I like this for the confrontation and civ like abilities cards.
Light/Easy:
For Sale - Simple Bidding game that easy to learn and has replay value. Great filler game.
Diamante - It is basically a game of chicken, with all players collecting diamonds from a mine and deciding when to run out. If your group likes to chatter and quote Indiana Jones you will get a good laugh.
One of the best sites for reviews and suggestions is www.boardgamegeek.com.
Old school, simple, but yet not simple at all: Scotland Yard
I’ve had the game for years and it never gets boring. It says three or more players, but you can play all five detectives vs. Mr. X with two players.
One other thing: if you’re into simulations, find some old Avalon Hill games. Some are still made, but others are long out of print, much to my disappointment.
I have 100ish German games in my collection and will be co-hosting an invitation only boardgaming event that will run four days next week (it takes place in a hotel conference room and is an awesome time). Some recommendations:
You said they were on top of you list and I agree that Puerto Rico and Power Grid are outstanding games. San Juan is light and fluffy, but makes a good filler as a card game.
St. Petersburg is also a fun ‘card game’ played on a board that still sees a lot of play. Amun Re is a bit heavier and plays best for 5 (but also good for 4) and is one of my favorites.
For Party Games, I really enjoy Time’s Up as well as all of the old standards.
If you want an excellent card game Tichu is probably the greatest card game of all time, and Mu has elements of bridge, but is sufficiently different with an alternate deck, a different style of bidding, and the bid winner choosing his partner, plus plays great for 4 or 5.
Among many others already mentioned above, I’ll add Corporate Shuffle to the list of ‘must have’ games.
Also know as ‘the dilbert game’, it is a version on The Great Dalmuti game. A very simple card game, easy to learn, that is enjoyed by many of my friends who don’t like games in general. An added attraction is that every card has a different panel from the Dilbert Comic, making the cards fun to read while waiting for your turn.
Excuse me now, I’m off to wrap my copy of Titan in acid free paper and double ziploc baggies for protection… $500 ??? Geeze, and I thought selling off my M:tG Alpha Black Lotus cards for $100 each was insane!
Oh, and wanted to add Attika with its constantly changing board and multiple ways to win, which plays awesomely for 2-4 players equally (a rarity in boardgames anymore).
You know, I nearly bought Totally Renamed Spy Game before I realized it was, well, a totally renamed version of Before I Kill You, Mr. Bond which I surmise ran into trademark difficulties.
I didn’t see anyone mention it, but one of my favorite board games is Allies and Axis. There are also some follow up games in the series, some of which I’ve played and others I haven’t (Allies and Axis Europe and I think there is a Japanese variant too which I haven’t played). Its strategy light, but its still a lot of fun if you have an evening to spend and 2-5 close friends to spend it with.
-XT
Had you kept them they would each be worth about twice the current value of a copy of Titan. And that’s selling to a store. They may fetch even more on the market to regular players as stores sell them for ~1500 each.
Enjoy,
Steven
Isn’t this called Axis and Allies?
You do indeed mean Axis & Allies. Recently (that is, within the past five years) they’ve come out with Axis & Allies: Pacific, Axis & Allies: Europe, Axis & Allies: D-Day and a new edition of vanilla Axis & Allies. The most annoying thing about this proliferation of spinoffs is that each one of them has a minor variant in its rules.
“Okay, does this one allow fighters to escort bombers on strategic bombing raids? No? Ok, that must have been in A&A Pacific. Wait, transports can carry armor AND infantry simultaneously? I thought that was in … oh, fuck, yeah, I guess you can do it.”
On the other hand, some nice game balancing has taken place - heavy bombers now only roll two dice instead of three, no industrial complex can produce more units than the value of the territory, the Atlantic has been split into a few more sea zones, the Sahara is now impassible, et cetera. The game can also be quite strategy-heavy once you’ve played it a good number of times, as the wise player will minimize the effect of the dice upon his fate, even though it cannot be completely eliminated.
My bad…yes, I meant Axis & Allies (its been a while since I’ve played obviously). I used to play it with a group of room mates in college and it can be quite engaging. I haven’t actually seen the original game on the shelves (I assume they still make it though), but I’ve seen the spin off games a few times.
-XT
I played a lot of Diplomacy in high school. This game was said to be a favorite of JFK. There are no dice to roll, so it’s purely strategic. Each player controls one of the major powers of World War I. During the Diplomacy phase, the players wheel and deal with each other, attempting to form alliances or concocting betrayals, whatever they can do to get ahead. After that everyone writes down their moves in secret and hands them to a neutral arbiter, who then determines the results during the Move phase. If all the players know the rules the arbiter isn’t strictly necessary, but it helps speed things along. Finally everyone who controls a factory gets to build new units in the Build phase.
Ya know, I keep missing the Doper Diplomacy threads somehow. Next time, the world will be mine! Muahahahaha!