It's worse than that as the 16K isn't all available to use. So that's where you start to get clever and look into compression of the data. There are lots of directions this could go but assuming you don't want a desktop (or laptop) computer involved in any way (remember the Arduino is a computer) and you can start / stop the music with a logic level you could code things for each light with a byte for each light that says how many half second cycles to go before changing state. This runtime encoding is like the compression in GIF images.
You might be better writing an application in say processing, so that you define your light show like a music application and then it generates a compressed file to down load to your Arduino.
Another option is that you could use the Arduino to generate MIDI data for a MIDI voice unit and have the lights go with that.
Lots of interesting possibilities.