This is a common problem with switching inductive loads, especially 120-220 VAC, using a
microcontroller system. The initial precautions include:
- adequate bypass caps on the microcontroller.
- reverse diodes across the relay coils.
- snubbers on the relay contacts [do google search on "snubber"].
If that doesn't fix the problem, well, some commercial companies have to go to truly heroic
efforts to get their systems working reliably.
Also, in general, you cannot drive a 5V relay directly from an Arduino I/O pin, as 5V relays
typically require somewhat more current than the pins can provide, so people typically use
NPN transistor inverters between the I/O pin and relay.