RGB LED audio spectrum analyzer - Bandpass or FFT?
Personally I would go (and have in the the past gone) the FFT route.  However I wouldn't use an 8-bit AVR, I'd use something somewhat faster.

My personal weapon of choice is the PIC32, which has more than enough power to do a good job of the FFT, but there are other good choices besides that - such as one of Atmel's 32-bit ARM chips (SAM3X for instance, like in the Arduino Due), or many of the other ARM chips that there are out there.

The trick with FFT is you need a good fast sample rate and enough memory to store a complex sample buffer.  Say you want 1024 samples (which would give you 512 FFT buckets to play with), at 16 bits per sample, plus 16 extra bits for the complex FFT component, you're talking a minimum of 4KB of RAM just for the sample storage.  Also, if you want it to be smooth then you want to be using DMA to read the samples in to one buffer while running FFT on another buffer, so a ping-pong double-buffer would increase that to 8KB.

With FFT you get half the number of buckets, or frequency ranges, as you have samples.  The frequency range is also half the sample rate.  So if you have 1024 samples recorded at 48KHz, that gives you a frequency range of 0-24KHz, with (24000/512=) 46.875Hz per bucket.

Reducing to 128 samples would give you 64 buckets, each at 375Hz per bucket.