And Spirit Tracks has a fun multiplayer game that my kids like. In fact they really liked the one in Phantom Hourglass too. Spirit Tracks' new multiplayer game supports up to 4 players via download play (only need one cart), so if they have friends with DS's, that's a nice choice for some multiplayer fun, not to mention the single player game!! Phantom Hourglass' multiplayer game only supports 2 players, but it also has online play, which is curiously missing from Spirit Tracks.
And don't forget New Super Mario Bros. DS. It's a great 2D mario platformer and it also has a really fun multiplayer download play game and other mini games. It's a great value.
EDIT: I'm regretting not having jumped on the Mario Bundle. It's no longer available, at least not for a reasonable price. I'd probably be happy with a metallic blue DSi without the bundle, but there is none.
EDIT2: note that Mario Kart's multiplayer game is limited when using download play. In particular the downloading players don't get a choice of character. That was a real bummer for my kids. So if you're looking for a 2 player experience, they are going to want 2 copies of the game.