The games that I have that I would recommend.
Tetris DS
It's Tetris with a bunch of new modes that add to, not take away from the experience. New remixes of Nintendo theme from ye olde days that are infectious and fun. Computers with adjustable levels and two kinds of puzzle mode are oodles of fun. WiFi multiplayer makes it more fun than a pillow fight.
Mario Kart DS
A series that has not gone wrong in the past continues in being perhaps the best racing game on the market. New courses as well as old ones, mission mode, new characters and karts. WiFi provides more opponents when you get to the point where you have all of the computers bested.
Metroid Prime: Hunters
I was worried about this one before it came out, I love the Metroid games (in both incarnations) and I didn't want them to make it suck wih the touch screen instead of releasing it on the Gamecube. My fears were aussaged when I picked it up, the screen provides full, reactive, and swift control. Interesting story, fun and challenging opponents. I still haven't beaten it yet, but I'm still playing it. WiFi (with new, selectable players) provides opponents that will kick your ass quickly, but it's a fun slide to the bottom.
Meteos
God, I must have logged about a hundred hours on this game. It's simple, addictive, and requires skill. A must have for the system. if you have a nearby friend, the multiplayer is amazing. If you don't, there are many ways you can set up computer battles so as to have a sliding difficulty level.
Advance Wars DS
I'm terrible at this game, but I still love it. Exactly what you'd expect from an Advance Wars title, with a touch screen that speeds up turns and a second front on some missions that add a new level of difficulty, it's a lot of fun and not just the same game as before.
Kirby's Canvas Curse
The funnest game I've ever lost (Like physically, I miss it so). Lots of fun, innovative, diffcult. A mix of speed and finesse. A definite need for the system.
I hope my ramblings haven't been too long-winded.