FF3 DS (very old school, retarded difficulty curve)
FF4 DS and DQ 4,5 are on their way hopefully. DQ4 and FF4 in 3D are out in Japan. DQ9 will be on the DS eventually.
Contact is an earthbound like RPG.
I wouldn’t suggest Heroes of Mana quite yet. Everything about it is awesome and well done except for the AI of your units, which is so stupid, it makes the game needlessly hard.
Puzzle Quest is an interesting but odd game. Its Dungeon and Dragons meets Bejewelled.
You can buy FF4,5,6 for the GBA (the DS has a GBA games slot).
There is a zelda game for the DS that uses the stylus.
2 great castlevania games, pseudo RPGs / platformers.
I know people that use XD memory chips to download games and roms and emulators and play NES and SNES games on their DS using the emulators.