It seems obvious, but if you want to build a robot you can truly interact with in a fun way, why not build a game-playing robot? Several Mindstorms inventors have latched onto this idea for some excellent creations.
A robotic blackjack dealer has been created. The dealer uses a special pack of cards with bar codes on them, so the dealer can read the value of each card using the light sensor. It deals out cards to itself and to the player, knows when either has won or lost, and keeps track of the score. The only thing it doesn't do is mix drinks, which would make the perfect Las Vegas experience.
Another impressive project is an attempt to implement a chess-playing opponent with a Lego that physically moves real chess pieces. Normally, these kinds of taxing programs are offloaded to the PC because it has more memory and a faster processor; then the move is passed to the RCX to execute on the board. The inventor of this project, Andy Clapham, is attempting to contain the entire chess-playing program (move selector and piece mover) on one RCX brick! So far, he has the chess algorithm working on the RCX, and there is about 6Kb of memory left over for the other functions. It will be interesting to see if this ambitious project is completed. If so, I'll definitely want to get my hands on the code and building instructions!
Turn-based games aren't the only interesting games created with Mindstorms. There have been some interesting sports robots that play soccer, hockey, and basketball. One Lego inventor even created his own pinball machine using the RCX brick to control the action.