Oh, and don't forget Ketsui! Amazing game, but not for everyone I suppose. EDIT: Didn't see Xerdo beat me to it.
If you like Retro Game Challenge, which is awesome, try a Japanese game by Namco that's called "Bokura no TV Game Kentei". It's so fucking awesome. Japanese Only - but it's really, really fun. Much better than Retro Game Challenge, which is still very good.
Legend of Kage 2 by Taito is good for some old school side scrolling action. Gegege no Kitarou - Youkai Daigekisen is yet another cool 2d side scrolling game. Commando Steel Disaster is a pretty good Metal Slug style clone, although it does get a bit repetitive. Bubble Bobble Revolution (I think) is the one good Bubble Bobble for the DS. I know there's at least one crappy BB but I think that's the decent one if memory serves me. New Zealand Story Revolution is another nice oldie. Classic Action Devilish is pretty nice, but I think the double screens make the game play a little bit awkward when the balls moving fast (Same goes for Arkanoid). Dementium the Ward and it's recently released sequel are probably the best fps games on the system. Moon would also be another decent DS fps. I also think the Hokuto no Ken Shin game on DS is one of the best to use the stylus. It's fast fun addicting and has some nice extras to unlock. As stated by a few others both Dragon Quests, Final Fantasy, Ketsui, Contra 4, Castlevania Order of Ecclesia/Dawn of Sorrow and Retro Game Challenge along with it's Japanese counter part are some of the best the DS offers.
...also try it if you like WarioWare. It reminds me a lot more of WarioWare Inc's Nintendo games section (just with Namco titles instead, obviously) than of RGC.
I prefer both Game Centre CX games over Bokura no TV Game Kentei, as the games in CX are full games the ones Bokura no TV Game Kentei are just parts of the full game. You never get the full games unlocked in that, the closest you get is all the minigames from the same game bundled together. But all 3 are good games regardless. Theres a ton of good ds games already listed in the posts in this thread, however lots of the good stuff are are only available as imports, but i happen to like amongst others...... Welcome home chibi robo Suujin Taisen Tingles colour changing balloon trip of love Space invaders extreme Everyones Conveni Item Getter Nanashi No Game 1 & 2 Doraemon: Nobita no Shin Makai Daibouken DS Doraemon: Nobita to Midori no Kyojinden DS Taiko No Tatsujin DS Meccha Taiko No Tatsujin DS Tottado! Yowiko no Mujintou Seikatsu The DS is pretty much my most played thing i own, it literally gets several hours every day of playtime & the game library is second to none. I love collecting for it & playing the many weird & fun games on it.