999, Hotel Dusk and Ghost Trick already recommended? My goodness - be still my heart.
Seriously though, I'll second all of those.
If you have any affinity for classic adventure games, Hotel Dusk will scratch that itch nicely, and has a very unique style to it as well. The story's a really interesting mystery to chew on and then resolve.
999 is at times more of a visual novel interspersed with occasional math puzzles, but the story it tells is great and the characters you meet are wonderfully written, and it has a few plot twists that will pretty much creep up on you and punch your teeth out in the best of ways.
Ghost Trick is an all-out fabulous game and, honestly, if you're faced with a choice between the above three, go for Ghost Trick. Whatever praise I could give it here wouldn't be the half of it. Unique gameplay, unique visual style, great story, fantastic soundtrack, absolutely worth playing.
I'd recommend Rhythm Thief as well. I'm a novice to the rhythm game genre, but I found it a nice blend of challenging and easy enough to grasp with rather nice music. If you like electroswing, or blends of big band with modern electronica, you'll probably find the music addictive.
Since you like Pokemon, go find a nice used copy of Pokemon Mystery Dungeon: Explorers of Sky. Nice RPG style gameplay and honestly a storyline that really impressed me. One normally doesn't expect that from Pokemon, but even compared to recent complexity of storyline in B/W one and two, it's about as jarring as leaning down to coo at a little fluffy kitten and then having said kitten drop-kick you three miles into the far distance. Except, you know, pleasant, so maybe more like getting up to hear the doorbell ring, expecting mormons there to preach at you, and instead finding your best friend has ordered you an extra large of your favourite pizza with cheesy breadsticks and your favourite soft drink, all delivered by the most comely deliveryperson the pizza place has to offer. Or maybe I am overrating it slightly because it reduced my usually stony-faced self to gross bawling tears with a plot twist, but I did have a family member dying at the time, so, you may want to take my reaction with a grain of salt given how easy to come by tears were at that point.
PMD is worth looking for, basically. You can probably find a copy for 12 bucks or so if you don't mind used. It's good. It's really good. You'll like it. (Explorers of Time and Explorers of Darkness are basically the same game, but Explorers of Sky has much more "bonus content" and a few other tweaks. Think of it like the difference between Fallout 3 and Fallout 3 GOTY Edition.)
Also worth keeping an eye out for is Phoenix Wright: Ace Attorney. If you're new to the series, you'll want to start with the first game, but they all pop up used fairly often. If you can't find it for your DS but still want immediate satisfaction of playing it, the first game's been ported to a few other systems, most notably iOS.
Speaking of iOS - I believe you can try out the first chapters of Ghost Trick for free and the first case of Phoenix Wright for free by downloading said apps from Apple's store onto your iPod or iPhone, and there are sales every so often so you won't spend more than 15 on the entire game in any case. They port pretty smoothly over and it's actually how I own them. Something to keep in mind if you want something of a demo before buying for either your iPhone or your DS.