If you like RPGs, I recommend the remakes of Dragon Quest IV and V, the Final Fantasy remakes, and Chrono Trigger remake. And to a lesser extent Dragon Quest Monsters: Joker. It's good, but if you played any other games in the series, it doesn't live up.
If you like platformers, I recommend the remake of Kirby Super Star.
If you are a super nerd, I recommend CrossworDS.
If you're Japanese, I recommend Phantasy Star Zero. It has free online play and plays similarly to PSO.
Oh, and Elite Beat Agents. Play that.
Wow, lots of remakes for DS.
edit: Dragon Quest V not VI. lol