Puzzle Quest
Wow. This game is seriously addicting; I had trouble putting it down to write this post. In fact, I kept playing even after the demo prevented me from leveling up. Puzzle Quest takes Bejeweled-style gameplay to a whole new level by adding skills, items, and spells. Unlike many other RPGs, it features an incredibly engaging and replayable single-player mode, and I can imagine that multi-player will be even better. It will also well suited for the PSP because each puzzle doesn't require that much time to complete, and the game is not as complex as a PC or console RPG. Puzzle Quest is a polished, rock-solid game that features incredibly thoughtful hints and context menus, which completely eliminate the need for tutorials or documentation.
The medieval fantasy theme fits well with Puzzle Quest's game mechanic even though I believe it is mostly irrelevant. At first I read all of story cut-scenes, but eventually I just skipped them. The art and the interface is attractive, appropriate, and consistent, but it's the game mechanic that is truly compelling. Alternatively, the designers could have chosen a futuristic theme with humans, robots, and aliens, instead of warriors, knights, and wizards. The story, art assets, item names, and skill names would have be swapped but the core mechanic could remain exactly the same.