...so your advise is: buy a better relay board?
Only if the relay-boards is flawed. If they are not made like that, and dangerous, i thing the noise is entering by the air.
Also, try plugging the power supply for the Arduino in another outlet, or supply the Arduino with power from your USB-cable.
What voltage are you powering the Arduino with ? As far as i can see, the wall wart you use is a rather old un-regulated unit, and a spike on the mains line will be carried over to the Arduino easily. As you have wired it, a load on your relays will induce a power drop on the wires supplying the wall wart.
Some things to try out:
1. Set the power supply for 7,5V.
2. put a load on a relay, a lamp for example, turn the lamp off by it's switch. try turning on the relay - what happens ?
3. power the arduino from your USB cable plugged into the computer.