1. Astro Boy: Omega Factor
-Must be played on Hard mode. (Limits super moves to 3 stock capacity.)
2. Castlevania: Aria of Sorrow
3. Metroid Fusion
4. Mario & Luigi SuperStar Saga
5. Pokemon Ruby Version
-I would recommend battling a local friend. Have both of you use a Gameshark and create a level 100 teams. That way you get to experience the great battle system and skip all the life wasting grinding. (read battle rules
here)
6. Megaman Zero
I'll write up more on them. Did not get around to playing what I've read is the best GBA game: Ninja Five-O. Also, did not play the Sonic Advance 2 and 3 games which were supposed to be half-decent. The Legend of Spyro: The Eternal Night got hyped up a lot on penny arcade forums because it was similar to Astro Boy: Omega Factor -- you might want to check that one out as well.