Mario vs. Donkey Kong 2: March of the Minis
I'm slightly disappointed that the difficulty never got absurd - sure, there were stages that I had to retry several times to get the gold, but I could have passed them with little difficulty. But in any event the game was a great and satisfying challenge on the whole.
The music wasn't incredibly memorable, but not bad, and the graphics are some of the best the second dimension has to offer. I haven't mentioned the story so far because there really isn't one. The replay value leaves something to be desired - there isn't much to gain from getting higher ranks or scores in the game's levels, and the Construction Zone has nothing in the way of instant gratification (though it can be fun if you've got the time to build it and a friend to play it).
I can't say how well you'll do with this if you're not already into puzzle games. The learning curve isn't the steepest, but the rewards are in the form of pride, not big fancy cinematics. That said, I feel really good about my time with this game, and for puzzle fans, this should be near the top of your list.
Progress: All gold stars, everything unlocked