Sonic Advance was and still is awesome, Sonic Advance 2 *even moreso*, don't have an opinion on 3. The Doom port was quite enjoyable back in the day, but you can have that on the DS so I'd skip it. Mario Kart Advance is the best game in the series IMHO, essential game you should try. Metroid Fusion/Zero Mission, 'nough said. It's just action, it never gets old, kinda like Contra. Advance Wars - a classic. Wholeheartedly enjoyed Golden Sun, but I see comments that it's too slow-paced, so it depends on your taste, really. Castlevania - Aria of Sorrow. Because it's Castlevania, again, it never gets old. Summon Night: Swordcraft Story 1-3 are *a must*, they're incredibly enjoyable and pushed the console to its limits as far as graphics AND interesting gameplay concepts are concerned. Chu Chu Rocket provided you don't have a Dreamcast. It's not AS good as the original but still heck of a lot of fun. Harvest Moon: Friends of Mineral Town if you like that kind of thing - it's hard to go wrong with a Harvest Moon game. Final Fantasy Tactics, simply because it's lots of fun, it's engaging and there really isn't that much of a quality gap between the PSX, GBA, PSP and DS entries in the saga - they're all solid games. Sonic Battle because it was a pleasant change in the sllightly stale "Sonic" series and I found it truly enjoyable. Customizing Emerl can really be alot of fun, and it bothers me why this game wasn't embraced by the fans more. I actually believe it'd appeal *more* to people who are not fans of the series because other than the characters and their sprites, it really hasn't got all that much to do with the story arc, and perhaps that's why it was "forgotten".
That'd be it from my list, I suppose. There are more, but it's best if you ease yourself into the "retro" feel first before you try out something "major". It's hard to overlook the shortcommings in the graphics department at first, but once you look past that, GBA games really have a spark of magic in them. They're not exactly "retro" just yet, but they're not "contemporary" either, they're just "different".