New Super Mario Bros - It's friggin Mario. It's a bit easy, but still fun to play. If you have a flashcard, someone's working on a great revival of Mario 3 using this game's engine. I played it when it was an early beta and it was off to a great start. Nowadays it has added levels and difficulty.
Castlevania: Dawn of Sorrow or Order of Ecclesia - I don't recommend Portrait of Ruin due to the forlced switching of characters all the time and the reuse of the areas to artificially lengthen the game. Dawn of Sorrow is the great continuation to Aria and even features a Julius mode that brings back the Castlevania 3 multi-character mechanic. Unlike Portrait, the characters are only forced to navigate a few obstacles. You can fight with any of the three characters with the same proficiency. Order of Ecclesia is simply modern Castlevania with a little difficulty added (for once). It's also the first canon female protagonist. Shanoa is not only pretty, but a force to be reckoned with on par with a Belmont.
Planet Puzzle League - If you've played Panel de Pon (Tetris Attack in the US), then you'll love this game.
Meteos - Think Planet Puzzle League, but your matches take off like rockets. You have to launch as many Meteos as you can and defeat your opponent. It's easily the most addictive puzzle game on the DS, and it remains overlooked.
Geometry Wars Galaxies - It's Geometry Wars for your DS. Arcade style gamers will love it.
Metal Slug 7 - This series shouldn't need explanation.
Mega Man ZX - Likewise. Stay away from Advent, though. It sucked. Its level design was lacking, the plot was worse, and playing as the bosses really wasn't as cool as expected.
Diddy Kong Racing DS - This game gets overlooked a lot. Unlike Mario Kart DS, there isn't an instant win character or tactic and the gameplay is more varied. It's a remake of the N64 version. Due to copyright issues, however, Banjo and Conker were replaced.
Zelda: Spirit Tracks - It's Zelda. And you're not on a boring boat! It's the first Zelda where Zelda plays a truly active role, too.
Pokémon SoulSilver - If you loved Gold and Silver from the GBC days, you'll fall in love with HeartGold and SoulSilver. Just skip over Diamond, Pearl, and Platinum. They (and Black and White) show a clear lack of good ideas. HG and SS are the only good thing that has happened to Pokémon since Crystal.
Etrian Odyssey series - These games are fun, but not for the faint of heart. If you pine for the days where you had to draw your map on a piece of paper and contended with enemies that were hard as nails and grinding was actually difficult, this series is for you. I friggin LOVE this series.
Izuna: Legend of the Unemployed Ninja and Izuna 2 - Like Etrian Odyssey, Izuna is a difficult game, but it's a roguelike (think nethack). Other good suggestions in the genre are Shiren the Wanderer and Pokémon Mystery Dungeon.
Metroid Prime Hunters - This is probably the most interesting FPS you're going to find for the DS. It's sci-fi, fast-paced, and has somewhat good multiplayer (as long as you don't cheese altforms or the Imperialist). If you prefer something a little different, I've heard good things about Moon and the Dementium games.
Cave Story (DSiWare) - This game is the poster child for indy gamers and developers everywhere. Developed by a single guy over the course of 5 years, Cave Story is a wonderful game close in gameplay to Metroid with a great weapons system, charming character design, and a story that stays interesting throughout the course of the game. It's also a bit difficult.
Radiant Historia - This game is an interesting mix of turn-based grid combat and the deepest time traveling mechanics I've seen in a game. This is what more RPGs should be like. Namely, the idea that your decisions actually have consequences and effect the story. The story is well thought out in this, since it's the meat of the game. The world is slowly turning to sand and two opposing empires are trying to seize what's left of the fertile land for themselves. Among all this, you play as Stocke, a man who works for one of the empires. One day, you're given a book that allows you to go back to any critical point in time after you've been there with the book. This book proves to be necessary to figure out why the earth is dying, why the empires are fighting, and how to solve the problem. In order to do so, you have to explore two separate but interlinked storylines and find a way to bring them together to avert the world's destruction. </soapbox>
Dragon Quest 9 and Golden Sun: Dark Dawn - I list these together because their core gameplay is the same. While Dragon Quest is more classic JRPG, Golden Sun actually has puzzles in it that force you to think. Dragon Quest is the longer, bigger game, though.
I think that'll do for now. I own a bunch of DS games, so more may come to me later.