Where's the music coming from?
...8 Channel SainSmart relays.
You do know that there are 12 notes in an octave, and some songs span more than one octave? 
Although almost no songs use all 12 notes, so the lights can represent differnt notes (a different key/scale) for different songs.
If you are "computer generating" the music, then [u]MIDI[/u] would be the best solution. You would make the light as-if you are making an MIDI instrument, except lights blink instead of sounds/notes. Then changing the song simply involves loading a different MIDI file. And, you can use any MIDI controller (or a computer) to and any MIDI instrument (or computer) to play the music. MIDI can play different instrument sounds (but not vocals/lyrics) and it can play chords (more than one note at a time). You can find MIDI files on the Internet, and the classical traditional Christmas carols are long out of copyright, so you should be able to find them free. The thing is... I doubt you can complete that project by Christmas.
The MSGEQ7 chip will respond to audio frequency bands, but two notes that are close together will activate the same lights. This is probably the simplest solution if you want to be done by Christmas. And, it will work with any CDs & MP3s that you have.
The 3rd option is to get a sound shield and "manually" program simple tones/notes and the lights together. That shouldn't be that much work (for a few songs) because once you write some functions (or a function) to take a note and duration as input, and create the tone & trigger the light, it's just a matter of entering/adding the notes & duration for the varous songs.