Reiner Knizia's Ingenious has one of the simplest rule sets of any game I have ever played. Five minutes out of the box, and you're playing a game with 1, 2, 3 or 4 players. For someone used to sitting down with a good rule set like others sit down with a novel, this was a pleasant (if reluctantly accepted) surprise.
Though its rules might be simple -- place your pieces on the board, and score points for similar symbols in any straight line out from the symbol -- the simplicity masks a depth of play that reveals a little more of itself each time your opponent screws you over or you screw him over without actually realizing you were doing it. The slow, but steady emergence of subtle strategies is the hallmark of a good abstract strategy game and the constant player feels rewarded.
Players gain a point for each pattern they match, and as the game progresses, they move the six different symbol counters down a track to mark their progress.
When the board is full, the lowest points scored for any symbol is the final score. So, even though you matched red like a fool, if you only got 2 points for the yellow stars, that's it for you. Knizia's decision to score the game this way forces players to re-evaluate their decisions constantly to keep track of possibility and not just current progress.
The game can be played in full in 15 minutes with 2 players and is quick enough that it offers that you'll find yourself saying, "One more game?" again and again.
N.B.: There's also a PC version from Merscom.