I would recommend you use solid state relay with zero cross. You are getting EMI pulses from the relay contacts. If you do not want to change relays place this one in a metal enclosure. It is very important you do not Power the relay with the Arduino.
The flyback diode has entirely fixed the issue! I ended up just using a 1n4007 as suggested. Thank you so much to everyone for all the help, in particular @Railroader.