How to go about making a light show that syncs to the music live?

realtime spectrum analyzer, direct audio input from microphone, and still enough oomph left in the lowly 328 to generate NTSC video. I made this a couple of years ago now, but the libraries (FFT and Video) are the same as then... but you would want to skip the video and instead PWM on channels for lights.

You might consider doing the fourier transformation on the AVR. It works quite well...