Riviera is the only one of the lot I've actually received and begun playing so far.
Oh, in that case, you must definitely get Golden Sun 1 & 2, best RPGs I own that I've played on the thing.
(beat both twice btw, wanted to collect all the Djinn in it, which I did in the end after many, many hours of play)
Tactics Ogre & FF Tactics Advance are also both excellent in my book as far as hand-held strategical games go, got over 40+ hours of gameplay in FF Tactics (took me 50 to beat, and started playin it again), though the game has too few story sequences in it. Tactics Orgre, pretty much the same, but with more story, and a good one at that.
The Phantasy Star game you mentioned, thats the Phantasy Star 1-3 port Sega made right? They're alright if you can stand the retroness of the game, I unfortunately couldnt.
My sis has the Fire Emblem games, I quite like the battle system, as to how it plays paper-rock-scissors in terms of who deals more damage depending on what weapon type your unit is using against an enemy unit.
I hope that they do something as good as that soon for DS or something...
Not from the same company, but Mario & Luigi2 is due out at the end of this month, now to pray it be as good as the first gem for the GBA. But yeah, I'd love to see what Camelot Studios can make on the DS, Golden Sun looked amazing (imo) for a 2d-RPG as far as handheld standards went, now if they were to take that team, bump up the 2d graphics for the higher-rez screen, add in some 3d hardware effects....