It depends what you're looking for. The DS library is so vast and huge and monstrous it's insane. It really has every base covered. Personally, I got the most playtime out of Advance Wars. I played through the entire campaign twice and then got addicted to trying all the different maps. If you can wait, get Advance Wars 2, and it'll take over your life. Picross DS has done the same thing to me recently.

picross
puzzle quest (if you hadn't got it for other system)
phoenix wright 1, 2 and 3 (in order)
trace memory (nice use of DS functionalities, game is rather short and makes you want more)
Dragon quest monsters joker (I prefer this over pokemon, both have their strenghs/weaknesses)
front mission DS (tactics goodness)
etrian odysseys (99.9% that you will die at least once very soon, can't find these anymore with easy rpgs these days)

it depends a lot on what kind of games you like.
my fav are puzzle, rpg, tactical.
not enough time to play.

@Galaki:

Have you played Hotel Dusk Room 215? It's the game Cing made after Trace Memory and is generally considered to be a great improvement. The art style alone makes it worth checking out.

Yeah i did. I liked Trace Memory more though due to clever use of DS.
Gameplay wise, Trace wins.

Get Hotel Dusk and Puzzle Quest. Hotel Dusk is amazing, but you'll only play it once. But then Puzzle Quest will have you covered for the rest of your life.

Brain Training. Both of them.
Mario Kart DS
New SMB

Dont bother with Castlevania. Same stuff as GBA games. Just replay those and you are fine.

Recommend Nintendogs - my GF seems to get tons of enjoyment out of it.

Suda51's Contact (play it through the end)

Trace Memory & Hotel Dusk 215 for Exploring Adventure http://www.youtube.com/watch?v=aGs-FhhlvqE http://www.youtube.com/watch?v=SYY3ocPMx9w

FF3 for graphic & gameplay http://www.youtube.com/watch?v=FMUWLDDehgY

Warioware for learning the basic function of NDS http://www.youtube.com/watch?v=8w3DmSZPnbI

Mega Man(2 games) & Sonic (2 games) for franchise

Metriod,Brother in arms,Dementium for FPS........try stylus for FPS http://www.youtube.com/watch?v=kmeMeEEVRnY http://www.youtube.com/watch?v=NFiEbQLDuUk

Trauma center for Medical experience??????

Metroid Pinball for Rumble Pak...

Both Dragon Quest for Japs??????

Clubhouse Games for 42 games

Elite for humor & music http://www.youtube.com/watch?v=5Ad3z9O4ooo

Race Driver: Create & Race for best Racing on NDS plus create your own track experience.This car is actually TOCA series, if you know it(This is a good game with super bad sales, support it if you can) http://www.youtube.com/watch?v=ETp9z7GirWA

Advance War: Dual Strike is a MUST

MarioKart as well (best version to date)

Puzzle Quest

Those should eat up a solid four to six months of your time (especially if you have friends to play against)

I keep hearing so much about Advance Wars. Is it really that great? I havent tried it but the screenshots dont look to appealing. I feel really guilty owning a DS since launch day, about 15 games for it, and I really never looked into AW. Is it a strategy game kind of like the Fire Emblems?