The way the Pi circuit is shown here.http://www.thebox.myzen.co.uk/Tutorial/De-coupling.htmlThe inductor is in series with the supply with a capacitor to ground on each side of the inductor.
It would look like you need to get some RC suppressors for the AC Relays. Whenever you switch off a coil you get are probably goint to get some noise - might get lucky and switch at zero crossing but...They make RC suppressors that you can get from an industrial suppliers. Check for an Allen-Bradley distributor.Another possible method is to put some ferite beads on the lines running to the Arduino board. ou are getting induced voltage spikes that are affecting the low voltage side of your control box.
You mentioned to use a choke on "either side", what did you mean by that?