Honestly, NSMB was a great disappointment, perhaps the only game I truly regret buying for the DS. Much better fan-made Mario games are on the internet for free. However, that is just my sole opinion.
Great titles include...
Mario Kart (how could you go wrong with this?)
Pokemon (if you are into that kind of thing...[I AM!])
Advanced Wars (great game)
Etrian Odyssey (only if you are into hardcore dungeon crawling that just requires countless wasted hours)
I found Castlevania: Portait of Ruin to be uninventive and almost boring, but I haven't tried the other Castlevania DS game.
Phoenix Wright: Ace Attorney - Trials and Tribulations, coming out later this month, is supposed to surpass all the other Phoenix Wright games, which are considered solid in their own right.
If you like puzzle type of games, you may enjoy..
Tetris (a classic)
Picross (IMO the most enjoyable puzzle game on the DS)
Brain Age
Meteos