I'll repeat what others have already said - get Fire Emblem and Advance Wars.

They're both very attention heavy, and they only allow you to save between scenarios, (which take about 45 minutes to complete on average,) so be aware that these are not good games for when you just want something to do while waiting for the bus.

Just repeating a lot of things said before, but hopefully that'll demonstrate how correct they are.

Castlevania games! I know you said you're not a fan of Castlevania, but I'm interested to know which one(s) you did play, because there have been a few different gameplay styles over the course of the series.

Golden Sun and Golden Sun: The Lost Age if you like JRPGs.

The Metroid games (Fusion and Zero Mission) and the Zelda games (a Link to the Past and Minish Cap) are essential unless you actively dislike those series. Yes yes yes. Whoever let Treasure make it was a genius.

Other games that deserve some consideration:
Baldur's Gate Dark Alliance
Max Payne

Very good faithful recreations of their big brother versions.

I also enjoyed Tom Clancy's Splinter Cell on GBA even though it's not quite Splinter Cell.

I really liked that King Kong adventure game, kind of short but quite interesting.

Also, while not technically a GBA game, get the GBC version of Daikatana if you can find it. It's actually quite good. Probably better than the proper PC version.

Advance Wars is ok, and Golden Sun 1/2 are both good. How exactly is a remake of the first Metroid better than the newest entry in the series proper?

Some repeats but whatever:

-Golden Sun and Lost Age
-Megaman Battle Network 1-3
-Final Fantasy IV-VI
-Legend of Zelda: The Minish Cap
-Harvest Moon: Friends of Mineral Town
-Metroid Fusion (Zero Mission is good too)
-Castlevania: Harmony of Dissonance and Aria of Sorrow

Less linear gameplay. In Zero Mission you are more free to explore like the Metroid series originally was. In Fusion you end up being told where to go by a computer most of the time.

Game & Watch Gallery 4
Advance Guardian Heroes
Bomberman Max 2 (either version)
Crash: The Huge Adventure
Spyro: Season of Ice
Spyro: Season of Flame
Spyro: Attack of the Rhynocs
Legend of Spyro: The Eternal Night GBA
Banjo-Kazooie: Grunty's Revenge (though it's sadly pretty short)
Konami Krazy Racers
Sword of Mana (prequel to Secret of Mana made by Magical Starsign developer Brownie Brown)
Donkey Kong: King of Swing
Mario Vs Donkey Kong (from before the Mini-Marios took over, it's much like Donkey Kong GB)
Yoshi's Universal Gravitation/Yoshi Topsy-Turvy

Um, you *do* know that Zero Mission is just the first Metroid remade right? So you like Metroid on NES more than Fusion?

While it is a remake, it's more like a remake with liberties.
There's enough different to distinguish itself from its original outing while including gameplay additions from Super and Fusion.

I can't stand playing the original NES Metroid now, but I greatly enjoy Zero Mission.
I do think that, as a whole, it's a better game and more fun than Fusion.
Super is still the best, though (of the 2D games).

Fire Emblem and Advance Wars have already been said.

I would add the Phoenix Wright/Ace Attorney games, although those are on other platforms so you might have already played them.

This whole thread is really reminding me what a great handheld the GBA was.

Structurally it's identical. So are you saying that the upgraded graphics ALONE make it better than Fusion, which has much better graphics itself than either Metroid or Zero Mission?

I just want to make sure I understand your assertion.

Astroboy: The Omega Factor is one of the better beat'em up games on the system. River City Ransom EX is also worth picking up. If I remember, Dragonball: Advance Adventure is also on the system, and I remember it being worthwhile.

So far ive bought

FF6
ff tactics advance
DragonballZ the legacy of Goku 1&2

Found
Pokemon leaf green which is strangely addictive