Ooo, this is a tricky one.
I made myself a starter kit when buying my first Arduino from Oomlout. I started with their Prototyping Bundle for Arduino (although it was a Duemilanove back then, not the Uno it is now), and added an LCD display, lots of wires, some tac switches, a pair of RGB LEDs, lots and lots of red and green LEDs, a book of resistors, some still-unused H-bridge ICs for motor driving, and some shift registers to my shopping basket.
The thing I added first after that was probably a battery box, for portable power.

What do you want to do?

You want to work on remote/wireless stuff? Get a radio of some kind. Bluetooth is already in your laptop and your phone. Turn that full-colour touchscreen into a wireless, graphical interface for your project with a simple Bluetooth to serial adaptor. If you’re using a 3.3v device, such as the ST ARM boards, or the Ti Launchpad, you can get away with the slightly cheaper one without voltage level conversion.
You like robots, or making things work in the “real world”? Get some servo or stepper motors, perhaps some relays. You can even get tiny stepper motors low enough power to be run directly from an Arduino’s pins- Gaugette
You want some help debugging? Consider an LCD dot-matrix display, or the super handy digital tube device. I’ve written a review of it.

Always useful

Hookup leads are invaluable on your test bench. Get or make some with tiny hooks on for grasping IC legs, and other component pins. A little wall-wart PSU is useful, or you’ll be always tethered to a USB port.

Advanced stuff

A logic probe and/or oscilloscope will save you a lot of debugging headaches- and not just in hardware, but in software too. A proper bench PSU is needed for a lot of tasks, with an adjustable output and current limiting.