Two RPGs I enjoyed on my DS were Rune Factory: A Fantasy Harvest Moon (the sequel to which comes out next month) and Puzzle Quest: Challenge of the Warlords.
If you're not familiar with the Harvest Moon series, it's basically a farming sim. Rune Factory adds an exploration/level advancement mechanic on top of that. So, while you start off running your farm, you eventually start exploring nearby caves and fighting the monsters within to learn of a plot by a neighboring nation to invade the nation in which you live. In addition to farming, you can learn to cook, smithing (so you can make your own weapson and such), and woo the bachlorettes in town (eventually marrying one, if you choose). You can also collect runes (which replenish your health & stamina) from fully planted plots of land (hence the name "Rune Factory," 'cause you can plant stuff IN the caves to help your explorations).
Puzzle Quest is a more traditional fantasy RPG except the combat mechanic is a Bejeweled-like minigame. It has a fairly standard story, but is pretty entertaining and the combat is surprisingly addictive, though I hear it's a bit too easy with certain character combinations (I played through as a Wizard, so I didn't have that problem).