You have a "real" problem here, as in real-world industrial control. Inductive
loads like fans and motors produce ginormous amounts of EMI [look that
up on wikipedia], and it's worse for AC devices. I've known companies
to spend many 10s of $1000 fixing their systems.
First, you need to do what you can to reduce EMI in the switched loads,
snubbers are usually the first line of defence. Then you might also need to
protect the Arduino power supply from EMI pickup, and also protect all
of the I/O lines. The first can require various forms of power supply filtering,
and the 2nd may be as simple as voltage dividers or transzorbs on the I/O
lines, but may require optoisolators.
This might all be a simple fix, or may take months, depending upon the actual
amount fo noise generated in the loads being switched. There is no simple rule
for fixing, just a lot of things to try to see what works. Good luck.