I'd also recommend getting an Arduino. I wouldn't go for the Mini or other shrunk boards, just stick with the Uno (or even Duemilanove if you can get it cheaply). It's important to get the DIP version with a socketed microcontroller, not the stupid SMD version.
Why is the arduino the right tool for you?
It's reasonably inexpensive for a development board, works quite well and is an exceptionally frustration-less experience overall. Yes, of course it's slow and the programs take massive amounts of memory, but you can easily create programs that work right away without having lots of (I'd even say any, if you're willing to learn) experience in programming. If you get frustrated easily, I'd highly recommend the arduino. It's not a toy like some other platforms, you can also do real C with it (in fact, you are doing real C with it, you're just using high-level hardware abstraction library functions most of the time; if you feel like it, you can do direct port manipulation easily), but you don't have to.
The arduino uses Atmel's AVR microcontrollers, and the programs you write can be ported to smaller AVR micros as well, depending on which functions you use. If you're just doing blinking LEDs, chances are you won't use much RAM, so it could be entirely possible to fit the stuff on an ATMega 8 or 48 or what have you instead of the default 328. The Arduino can be used as a crude programmer for AVRs, so it's certainly doable to develop your programs on the Arduino, then optimize the code a bit to fit on the smaller chips and flash it to an ATMega 8 for use in your circuit. ATMegas are easily available and not too expensive, so I'd really stick with the Arduino.
Of course, you can use other chips as well or even program the AVR with an AVR programmer. But honestly, I wouldn't bother. You're not building thousands of LED circuits, so individual MCU price is not of great concern. The fact that you didn't already start programming microcontrollers for your stuff just tells me that you'd be quite unhappy and frustrated by using "normal" MCU development solutions.
Of course, if you want to do it, get some AVRs, PICs or even the cheap MSP430 value line devices, they'll all work reasonably well.