If you like Elite Beat Agents, it might be worth importing one or both of the Ouendan games. Gameplay wise, they are exactly the same, except with different music and stories. They can be played and (mostly) understood without knowing a lick of Japanese. Of course, if you can’t stand Jpop at all, then pass it by. Note, the DS and DS Lite have no region locking and the DSi still lets you play older games regardless of region, so importing is no hassle at all.
If you like platformers, New Super Mario Bros. and any of the Castlevanias are great. Super Mario 64 DS is also a strong title. Oh, and Yoshi’s Island DS is great, too.
If you like puzzle games, Meteos is quite good (dunno about the Disney themed one mentioned before), Picross is fun yet relatively easy logic puzzles, and New York Times Crosswords Puzzles delivers exactly what it promises in a good package.
If you like platformers AND puzzle games, get Henry Hatsworth in The Puzzling Adventure. It combines platforming and a Tetris Attack style puzzle in a charming package.
If you like RPGs, particularly of the action variety, The World Ends With You is great, and I hear good things about the re-releases of Final Fantasy IV and Chrono Trigger, though I’ve not played them in this incarnation.
If you’re looking for casual games to play with friends, I hear good things about Clubhouse Games. Lots of classic card and board games in a solid package that allows multiplayer using only one game cart.
If you have any fondness at all for tower defense games, Ninjatown is an extremely adorable, great game.
If you like retro, NES style games, Retro Games Challenge is pretty neat.
And of course, Mario Kart. Everyone loves Mario Kart.