I second Herg's Solitaire - something like 30 variants of Solitaire on the GBA. It's even multiboot-capable so you can eject the cartridge after getting in-game to save battery power.
Other recommendations depend on whether you want games or apps. If you want apps, use GSM Player for music playing, GBA JPEG viewer for images, METEO for videos, Book Reader for text files, GBA WinS for an interesting windowing system with a couple games, DanTE Advance for a quick text editor (once you get used to its text input system), Paint Master for a paint app, and Scrabble Dictionary for a quick spell checker.
If you want games, I'd recommend the GBAdev 2004bit competition cartridge, Luminesweeper, Lockjaw (or Lockjaw: The Overdose), and SFCave (way too addicting).
Then of course you've got your emulators: PocketNES, SNES Advance, Snezziboy, Goomba Color, TI83emu, SMS Advance, etc.