Amazon.com has Quirkle and Quirkle Cubes. The actual game is for 2-4 players, but like ElizabethN said you can also play with them by yourself. I believe it is rated for 6 and up. Pretty much anything by MindWare is good! As far as that goes anything by ThinkFun, the makers of Rush Hour is also good.
I just checked - Amazon.com also has Pentominoes and they are as you described above - reminds me of Tetris. I also just saw this which is sort of similar.
Katamino -
http://www.amazon.com/Gigamic-8051-Katamino-Game/dp/B0009H9SUC/Tantrix are also a bit like Pentominoes - flat tiles with colored squiggles. You can try to match your tiles to a specified shape or play a game with other kids where you take turns playing your tiles while matching the colored squiggles to form a puzzle.
We liked the flip cards of Brain Quest better than the books. The books are more like workbooks compared to the Q/A of the cards.
There are "extreme" dot to dot and maze books, which was what I was thinking when I mentioned those - probably like what is on the site you mentioned.
