+1 Pushmo/Pullblox
+1 Crashmo/Fallblox
These games are refreshingly challenging! Particularly Crashmo, goodness. That game dragged me up and down the curb within the first twenty levels!
(Of course, I'm not exactly a puzzle game aficionado, but I'm sure there's enough challenge in these games to satiate even the most masochistic of puzzlers!)
+1 Legend of Zelda: Link's Awakening DX, The
Honestly, there's absolutely no reason not to get this game if you haven't played it already. Heck, I've played it countless time before, and I still loved it this time around! It's an unequivocal classic, with all the defining elements that the series is renowned for (well, save for Ganon, I suppose!).