CocaColaKid,

As Steve has already mentioned, best would be to toggle the relais at zero-crossing only.
This would not only reduce EMI-noise, it would also increase the relays lifetime.

There are many ways to achieve this, but we would need to have a look at your schematic to point you in the right direction.

In any case you'll need a zero-crossing detector for this.

What I have done is:
put a 74x574 (8-Bit D-Latch with Clock) between the PIC port (I2C IO Expander in my case) and the relay driver.
and let the ZeroCrossing detector clock the latch.