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.
Free Online Ingenious AI
http://www.marquand.net/index.php?topic=ingenious
This is a fan made Java version of Ingenious.
The free trial licensed version from Merscom is available as noted above.
Simple fun
Along with Dorra's "For Sale" (which, if you haven't featured it already in this slot, you should), this is one of those games that you aren't completely sure was invented - more discovered.
Those people with no proper sense of spatial relationships (like me!) should steer clear of a game that's all about spotting patterns and knowing when to exploit them and when to block them. I am terminally dreadful at it; even the crappy AI versions out there can beat me hollow!
It should be a much better known game than it is... but there's still plenty of time for it while the more complex and over-wrought games come and go.