Here's a simple formula for engaging games: existing game + RPG. Mario Golf's core game is boring computer golf: choose a club, aim a stroke. press the button. But wrapped around that is an RPG. There's a world to explore, a character to level up, little quests. The core game is fun but shallow; the RPG gives it depth. This same mechanic works with the Tiger Woods golf series, action games like SSX and Tony Hawk skating, etc. There's even an MMOG version of this, the awesome Puzzle Pirates.
The latest stealth hit game to do this is Puzzle Quest. The core game is the match-three game Bejeweled. But wrapped around it is a high fantasy world of quests, monsters, character levelling, etc.
I've only played the PC demo, but it's clear the RPG elements add a lot of depth. Clearing rows of gems from the board gives you "mana" in one of four colours. Your character specializes in certain colours. You also specialize in certain special moves that manipulate the board in different way. As you specialize more in the RPG, the way you play the puzzle changes.
The game has pretty good reviews, although it looks like the PSP and NDS implementations are a bit weak. It's also getting a lot of buzz. Apparently no one thought it would sell well because it's pretty hard to find in stores. Amazon lists a 2-3 day delay on the order. In the meantime, try the PC demo.