pic16f output expander
Try this,
Leave your circuit as it is for the time being with I2C devices, if you use say 3 line to 8 decoders, you will only be able to drive one relay at once. There are of course ways round this, but for the moment leave as is.
Try having all your relays away on a separate board, say at least a few inches away prom the Pic. Now the important bit, take the 0 (ground) lead from each board back to a common 0 point, with no other possible ground returns. via chassis etc. I had the same problem trying to control several machines with a Micro, they were all earthed at their respective supply connections, The Micro was going crazy with erratic operation. Removing the grounds and then taking them back to a sing point completely cured the problem.
If this does not cure it, I think you need to look at further supression methods as well.