What watt bulb is that? Maybe try a smaller watt bulb, and some extra caps around.
Are you running the arduino and the lights off a small extension cord? If so, split them up. Use a different AC plug for each.
Rather than a mechanical relay, you will get less noise by using SSR designed for AC.
If you have to user mechanical relays, make sure you have protection diodes, snubbers, and proper drivers for it.