First of all, Riviera sucks horribly, and anyone who complained about inflated enemy health in Metroid Prime 2 or Mario and Luigi 2 or several other games would probably agree. I didn't even think it was possible to hate a game with one male character and five females, but yes. Yes indeed it is.
Anyway... In order of descending greatness:
-
Pokemon Emerald, and either Pokemon Fire Red or Leaf Green - First because they're insanely deep RPGs (at least after you get past the toned-down main quest), and secondly because, really, nobody's GBA collection is complete without the system's best-selling games.
-
Advance Wars 2 - Some argue that the AW1 tutorial is better for learning the game. I say that the entire AW2 campaign is better since you actually have to use all the characters, and in levels where they can show off their exact specialties. At any rate, since you liked Fire Emblem, this is a "gimme" recommendation, and I'd argue it's even better than FE due to less linearity and more replayability.
-
Mario Tennis: Power Tour - Awesome sports RPG with some really entertaining minigames on top of it. The opening takes about 12 minutes of dialogue, so there's that to consider, but should make up for it with about 12
hours of raw fun.
-
Any Castlevania game - Circle of the Moon had the largest print run, but will still be near-impossible to find, and the double pack of Harmony of Dissonance and Aria of Sorrow is the best value... but will also be near-impossible to find. Still, if you can manage to track them down, they're worth your while.
-
Metroid Zero Mission - Only slightly less worthwhile than Castlevania, due to lesser length but much greater replayability. Recommended over Fusion since Fusion is more linear.
-
Kirby and the Amazing Mirror - Another game with the same exploration style of Metroid and Castlevania, except it's more of a beat-em-up than an adventure title.
-
Tactics Ogre: Knight of Lodis - I'm guessing you won't be able to find this, which is a shame, but if you happen to, buy it. Just a great strategy RPG, way better than the abomination known as Final Fantasy Tactics Advance, and actually even better than the classic that is the original Final Fantasy Tactics.
-
Kirby: Nightmare in Dreamland - It's not Kirby and the Amazing Mirror, but it's more than good enough.
-
Drill Dozer - Ships on February 6th. Having played the Japanese version, this is a fun platformer with a lot of completely off-the-wall situations... Innovative and entertaining.
-
Tales of Phantasia - Ships on March 6th. I actually haven't played this, but apparently it's a really good action-RPG. Tales of Symphonia gives me no reason to doubt that that's very true.
-
Final Fantasy IV Advance - Slowdown issues hamper an otherwise great RPG. And yeah, the plot moves absurdly fast, but it's pretty irrelevant, really, when the game is this fun. If you can, hold out for FFV (I'd put it above FFIV but still below Drill Dozer) and especially FFVI (which would be above everything on this list other than Pokemon), but they don't have release dates yet, so who knows when they're coming out?