The Arduino Platform (ATmega)
The Arduino Platform is a collection of great and inexpensive micro controller boards, based on Atmel's AVR product line. The most popular chip is probably the ATmega168, but many people have started to replace it with the pin compatible ATmega328P. Lately the ATmega644 got more and more popular for more demanding projects.
The Arduino community has also created a very intuitive software environment, which can be downloaded from here for free.
Arduino Board(s)

The Arduino Diecimila is a great for beginners. It has been updated and is called Duemilanove now.
Boarduino

If you are a little more adventurous - the Boarduino is a better choice. You can buy a kit from Adafruit webshop, but you have to solder it yourself. The advantage is, that the footprint is very small and you can choose what kind of connectors you want. I used terminal screw-blocks, which makes it really flexible.
Sanguino
For experts is a monster board called Sanguino. Kits can be bought from RepRap. More memory, more I/O pins, more...
LED Tutorial
Only $2 and 20 minutes work. It is great to learn about basic programming, animation, and color mixing.
Only $5 and 30 minutes work. It is great to learn about basic animation, but also useful as a bar display.
Extension of the early prototype. It is great to learn about basic animation, but also useful as a bar display.
30 LED
Other Projects
Connecting a two or three axis accelerometer to an Arduino.
Simple input device - 3 potentiometers for analog inputs.
Only $2 and 30 minutes work. It allows to connect the Arduino to a TV (RCA).