The first is Stack. It's available commercially, but it's really too expensive for what you get. There is, however, a cheaper two-player version available now. There used to be rules for the game on the net, but for the life of me, I can't find 'em. The Bone Roller's Guild has a link, but it's dead. Basically each player has 14 dice of one color. At the beginning of the game, both players roll all their dice. The rest of the game consists of making "stacks", by putting your dice on your opponent's. At the end of a round, all dice of your color at the top of a stack give you points. For about a month, Shelly and I found ourselves dragging the dice-bag to every restaurant we visited so we could finish our big 1,000 point world-championship game.
Another great one is Raj by Winning Moves. Unfortunately, the game appears to have been discontinued, although a couple of online vendors still claim to have it (1, 2). I saw copies at a local MacFrugal's for $4, which is a steal. It's a neat little bidding game in which you bid on tiles with bid-cards. It's a great mind-game in which you have to try to outsmart your opponent in your bidding. If you can find a copy, I heartily recommend it.
Anyway, I mention these because I love games that are very simple, yet very elegant. I'm always envious when I come across a game that's dirt-simple, yet is tons of fun. Both of these games have a great balance of strategy and luck, yet only require a couple of minutes to learn. Large-format games, like tactical wargames, are interesting, but they've got so many rules that they lose their elegance. In much the same way that it's often more difficult to tell a rich story in 100 pages than 1,000, making a game with simple rules that doesn't get boring is a feat to be proud of.
I'd love to be able to come up with one of these someday.