chuckyx:
I will consider this in future drawings!
Substracting the bias is not necessary as I just take other low frequency bins and omit the 0 Hz one for my calculations 
Right. if you are using FFT you can ignore the zero Hz bin.
I just connect the project to my laptop or phone, so no high power.
My cheapo oscilloscope read some negative voltage (around -0.13 V) when I got to higher frequencies with a tone generator on my web browser. I didn't worry too much about that and my arduino survived for hours now 
With the bias it should (hopefully) never go negative. If it does, it will go over 5V by (approximately) the same amount, since the AC audio signal swings (approximately) equal in the positive and negative directions.
The signal ends with the arduino since I have a Y splitter, what ever I to the signal shouldnt affect the actual audio.
If the signal goes negative (into the Arduino, after the bias) or more than Vcc, the signal can be distorted. This is unlikely to happen, but you need to check the raw ADC readings, not the FFT.
I actually just had a 0.1 uF lying around, I read somewhere I should use electrolyte ones...
...So 10k may have been a little bit too small?
Yes. You are loosing bass. Try the link I gave you, and remember the resistors are effectively in parallel for the AC signal, so that's 01.uF and 5K.
❝For a low level input signal you may want to use the internal reference of 1.1V, and adjust the voltage divider accordingly (10:1). I'm not sure but eventually a 1:1 voltage divider from AREF to Gnd should work with any reference voltage.
What would be the advantage of that? Getting a higher resolution signal as my circuit doesn't have an amp?
Yes. Higher resolution and more "sensitivity" … Bigger ADC readings...
❝That seems like a great idea but the ATmega datasheet says:Maybe you could "get away with" 100K or 1M resistors. It doesn't have to be "perfect" for a lighting effect so that might work!
So 10k may have been a little bit too small?
This is only if you use Vref for your voltage divider, and switch between the 1.1V and 5V references in software. For example, you can't use the normal 2.5V bias with the 1.1V reference (you'd just max-out the ADC read 1023 all of the time).
❝...I automatically switch between the 5V and 1.1V reference depending on signal level, but I use a peak detector (additional circuitry) so my signal never goes negative.
You cannot use a peak detector with FFT. There is no audio out of it, only varying DC.
I also use a variable reference/threshold set in software.
This seems to be worth keeping in mind when I advance my project and correlate the intesisty of the light to the intensity of the signal.
So far I tested it for one party evening and it went fine, but I really need to work on some input detection b/c as is you shouldn't change the volume on the laptop but on the speaker itself
I'm not using FFT so my situation is simpler but besides switching to the 1.1V reference with low-level signals, here's what I do -
I take a "sample" of the "loudness" once per second and save it in a 20-element (20-second) [u]circular buffer[/u]. Then, depending on the effect I use the average or the maximum from that array (buffer) as a threshold or reference. You could also map() that the actual range to LED brightness, etc.
I get good results when I change the volume or with quiet & loud songs. My "simplest effect" is a "flicker" effect that turns the LED/light on when the signal is above average and off when below average.
I've got a "VU meter" effect where the top of the meter is the maximum and the bottom is the average. That gives a lot more "meter action" than a real meter, but it's completely useless as a meter since it's constantly re-adjusting itself and the increments between the LEDs are meaningless.
If you wanted, you could make separate thresholds/references for each color/band, or you could use the overall volume.
Note that there is more energy in the bass & mid frequencies so you might want to adjust for that. Of course, you're not getting a "true-spectrum" when you start monkeying with the readings but it might make a better display!