Yeah, you could say I'm a little late, but I just never got around to getting one when they were current. Was too busy playing tetris on my gameboy colour to even think about getting another handheld.  
 
I'm not interested in any of the pokemon titles though, I imagine they're good, but I'm looking for something a bit different.

metroid zero mission + fusion and golden sun 1 and 2 is a good start. 
 
EDIT: OH and advance wars for sure.

Golden Sun 1 & 2 

I use to play soo much goddamn tetris on gameboy. Anyway, if you're a fan of Super Metroid, make sure you pick up Zero Mission and Fusion. Both are awesome games.

Why the hell haven't I seen a single Fire Emblem recommendation yet?

Zelda: A Link to the Past, Puzzle Fighter 2, Wario Ware, Super Ghosts and Goblins (zomg it lets you save so you can finally see the end of one of the top 5 hardest games of all time), Pokemon Pinball is great for on the crapper, lets you save your game so you can build insanely high scores over time. I had one game last a year before losing the last ball.

The one thing you should be concerned with is you need to remember these are old game carts. The batteries in them that save the games are dieing out so if you get a RPG like golden sun, it might not be worth it.

Mario Golf: Advance Tour

Metroid Fusion.

Glad to see Metroid, Advance Wars and Fire Emblem already mentioned.  
 
If you can find it, Gunstar Super Heroes is a TON of fun, probably my favourite lesser known title. 
 
Also can't go wrong with a DK Country or Castlevania game. 

@Vegetable_Side_Dish: The first 2 castlevanias blew. Aria of Sorrow trumps them all by far.

Pokémon Emerald
Sonic Advance 1/2

Good recommendations so far, I'd also add Zelda: Minish Cap and the Castlevania games.

@Claude said:

Mario Golf: Advance Tour

YES!

Um, also Mario Kart: Super Circuit and Rayman Advance.

Pokemon Trading Card game, I fucking loved that game.

If you like Pokemon, any Pokemon game will do, Zelda Minish Cap  

@Vegetable_Side_Dish: The first 2 castlevanias blew. Aria of Sorrow trumps them all by far.

• Advance Wars/Black Hole Rising
• Rayman Advance
• Metroid Fusion
• Minish Cap
• Superstar Saga
• Final Fantasy Tactics Advance
• The Sims Bustin' Out
• Two Towers/Return of the King (kind of like Diablo)

Advance Wars / Black Hole Rising.

Warioware, Metroid Fusion, Minish Cap.

Wow, so I've got a lot to choose from the looks of things. Some of the games cost more than I paid for the system, which sucks but isn't surprising.

Metroid Fusion + Zero Mission, Advance Wars 1+2, Mario & Luigi. I especially loved Tony Hawk 4 (I think). POKeMON Emerald, but I had Ruby. I actually found the cartridge on holiday in some grass.
 
I'm quite jealous of you, getting a GBA now and getting all those titles so late. You can end up getting 20 titles for like $50 or something. 
 
So jealous.

So... why no emulator? Nintendo doesn't make Game Boy games anymore, so it isn't stealing anything from them or the developers. I'm just wondering why you'd pick up a Game Boy now. 
 
If you must have the cartridges, why no DS Lite? You could have a brand-spanking new DS Lite and be able to play all GBA games and all DS Lite games. 
 
Recommendations. Right-O. Well, some of these have already been mentioned, but I'm going to mention them again because they deserve it. 
 
Metroid Fusion 
Metroid Zero Mission. 
Castlevania Aria of Sorrow 
Final Fantasy VI 
Golden Sun 
Golden Sun 2 
Sonic Advance (any one of them) 
Donkey Kong Country 
Donkey Kong Country 2 
Megaman Zero 3 
Megaman Zero 4 
(Never played MMZ 1 and 2, so can't comment. I hear they're legendarily hard, though.) 
Megaman Battle Network 3 
Megaman and Bass 
(...what? I like Megaman games)  
Crash Bandicoot The Huge Adventure 
Mario Advanced 3: Yoshi's Island
 
And that's all I can think of at the moment, though I used to have like a million Game Boy Advance games laying around. They're still around... somewhere...

@Jasta said:

Pokemon Trading Card game, I fucking loved that game.

You can play the TCG online for free. It's a lot better than that old clunky Gameboy Colour game.

@believer258: It was boxed and in very good condition and a great price, I was actually considering just going for the DS lite, but I'm a bit of a collector and I knew I would regret not buying it. 

Tactics Ogre: The Knights of Lodis
The Lord of the Rings: The Twin Towers

Mega man Battle Network games. 
Fire Emblem 
Everyone else's recommendations!

Wario Ware Twisted and Pokemon.

Golden Sun 1 & 2.

Why the hell haven't I seen a single Fire Emblem recommendation yet?

Just came here to say Fire Emblem :)

WarioWare Inc. Mega Microgames 
WarioWare Twisted 
Super Mario Advance 3: Yoshi's Island 
Zelda Link to the past 
zelda minish cap 
metroid zero mission 
metroid fusion

Advance Wars & Pokemon Ruby/Sapphire/Emerald

Like others have said, Advance Wars and Fire emblem are great games.

pokemon. any/all of them

@People recommending Pokemon: 
 
It helps to read the OP. 

Golden Sun and Golden Sun The Lost Age.

Those are the only two GBA games I have gone back to.

You should only play Golden Sun if you're immune to insultingly bad repetitive jrpg dialogue. There's a great battle system there, but the characters act like they have some sort of congenital mental disorder.