turning on 4 1000w flood lights at once with arduino

The resistance of the halogen lamps will be very low when off, so when you switch them on you will get a surge of current as mentioned by jackrae. I expect the surge will be very brief, but I have no idea how big it will be. I believe a fuse may tolerate five times its rated current for quite a while before it blows, so a 13A fuse might take 65A very briefly. The problem is everything else in the circuit also has to carry that current.

As this is some kind of show I guess the leads to the lights could be long so you want to be sure the conductors are the right gauge for the length, and you don't want to keep any slack cable coiled especially on a metal drum.

I don't know how efficient halogen lamps are at producing light, perhaps there are other lamps that give more light for less power.
You should certainly experiment with a single lamp to see if it gives the effect you want before committing to a final solution.

The strobe idea sounds like it might be a good one.