Well, I enjoyed Crash of the Titans. It's a 3D platformer with some combat. It's also linear like the PS1 games. If you liked the PS1 games, you'll probably like this. It's short though.
Dementium is a really impressive 1st person shooter. It's a bit redundant though. You explore a sanitarium, but the environments never really ever change. It's pretty scary though if you're into survival horror.
Another fun shooter is Bionicle Heroes. Don't be fooled by the Lego license. It's a fun FPS.
I also liked Dragon Quest Monsters Joker. It's a over-shoulder 3D monster collecting RPG. It's a nice alternative to Pokemon if you've grown tired of the sameness of Pokemon (like me).
Robocalypse is an excellent RTS. It's come the closest to PC RTS games I've seen on DS.
Civilization Revolution is pretty fun. It's like the PC games. Has some flaws, but if you liked the PC games, you'll probably take a shine to this.
Chibi Robo is a neat park simulator. It's fun, but not for everyone.
Pac n Roll is a game that reminded me of Super Monkey Ball. You use the stylus to roll a transformed Pacman around 3D levels. It's simple fun.
Kirby Canvas Curse. Probably one of the best uses of the stylus I've seen. You draw paths for a ball-shaped Kirby to guide him through levels.
Kirby Super Star Ultra. One of finest classics on the Super NES just got a DS remake a few months ago. Although not innovative like Canvas Curse, and not using the stylus much, it's an awesome 2D platformer!
Zubo is a neat little rhythm-based RPG. I haven't gotten very far in it, but I liked it.
Soma Bringer is an excellent action RPG. It uses 3D characters on 2D background. There's I believe a near complete translation now.
Tales of Innocence. It's only in Japanese at the moment, but a work-in-progress translation is being done by the same people who did Tales of Phantasia on PS1.
Viewtiful Joe Double Trouble captured the look and feel of the Gamecube games really well. That is, if you can get over the poorly implemented touch gimmicks. If you can, it's awesome.