The best traditional and strategy RPGs on the GBA are Riviera: The Promised Land; Fire Emblem; Fire Emblem: The Sacred Stones; Golden Sun: The Lost Age; Mario & Luigi: Superstar Saga; Shining Force: Resurrection of the Dark Dragon; Final Fantasy IV Advance; and Tactics Ogre: The Knight of Lodis.
I consider Riviera the best of the bunch -- though it has its detractors, go read the game's appreciation thread to get an idea why it's so awesome. Completely, brilliantly innovative gameplay, a great and well-written story (one of Atlus's finest localization jobs), outstanding music, and some of the best graphics on the GBA (hand-drawn sprites and backgrounds).
Golden Sun 2 is... among old school traditional RPGs, one of the finest. Lots of random battles, but the battle system is excellent -- very, very fast-paced with some nice strategic elements thrown in. There's also a really nice character customization system that replaces a Final Fantasy-style class system with something... in many ways much cooler, since there's a great deal of flexibility in it and there's some sidequest-collection tied into it, too. There's also a ton of content in the game -- massive world, a ton of optional sidequests / extra dungeons / hidden special powers to find. And best of all, it has some of the finest level design I've ever seen in a traditional RPG -- enormous dungeons loaded with fantastic puzzles.