Disgaea DS is an often overlooked game that's amazingly complex.
(Rated T, DS, ~19.99, I give 4.9/5)
It's a strategy RPG, but the feel of it's completely different from most games. The characters are awesome, the gameplay is good, and WOW content. The main storyline can be beaten on about Lv. 70, but the level cap is 9999. That's right, nine THOUSAND nine hundred and ninety nine. The final optional boss iirc is on 6000, and he's really, really hard even if you're at 9999. There are 8 different endings, two different play modes, and penguins, dood!
To give you an idea of how it runs, I'm at 140 hours on my game right now. I've gotten 4 endings, and my highest character is on 1250. And I am absolutely not bored!
Also: Radiant Historia (DS, E10+, 4/5)
It's a fairly new DS game, and the idea behind it is rather strange. You skip between timelines, filling in holes, gaining skills, all to advance the story on two different fronts. It's interesting, because for an RPG it focuses very little on battling. The plotline (s) are the main focus, which is nice.