Wow, something about reading this thread makes me feel like I'm so... jaded. If we're keeping this to a discussion of NDS games with great/"epic" storylines, then I can hardly recommend much that I think fits in such a catagory. Don't get me wrong - I enjoyed playing a lot of games and I still have many to finish (Apollo Justice, Hotel Dusk, FFCC RoF for some examples).
But FFTA2 for example? Horrendous story, but I had fun anyway. Maybe because I've played FFTA(1) and was expecting something better than the "sucked into a book" crap, and because the Tactics Advance series is always being compared to FFT (PS1).
Maybe certain other games feel too cliche, also. Currently playing Soma Bringer, but I think I better finish soon because the story is wearing on me a little. The game is fun, but amnesia, and then some...
I found the storyline in "The World Ends With You" particularly engaging (mostly because you spend a good amount of time wondering what the hell is going on - especially after "days" go by... and if you're any kind of completist person, you'll do the special reports thing at the end too.
I liked Trauma Center, and I need to finish the second one. A little out there with the science but hey it's a video game - and maybe the world can go in that direction someday in the future. Maybe the storyline is a little cheesy but it compliments the gameplay very nicely so it's even more enjoyable.
Played Zelda: Phantom Hourglass, but maybe if it wasn't kiddie Link, I'd think twice about replaying it. Otherwise, it was an enjoyable play but not suuuper engaging with the storyline.
FF3, FF4 - FF3, not much story and this has already been covered. FF4 was one of my favorites, maybe because Kain and the Dragoon class is so damned cool, but ok. The main character is a Dark Knight and he has problems with being "Dark," in a way. Plus, there are some other important people in the story that make the game what it is, I feel.
Phoenix Wright (series): Excellent, but I can see where some people don't enjoy this. Lots of different stories span the games and character lives, and many are connected with each other...
I will take a look at Front Mission since it seems along the lines of something I'd like and haven't tried yet.