Arduino 16x2 LCD weird symbols after relay-switch
Given your setup it is likely that you have an issue similar to a customer of mine earlier this year.
Under EMC testing, his apparatus did not pass the test for intense external emissions.  The reason: the wires between the main board and the LCD board were long, unshielded and high impedance (>1 Ohm).

Your setup provides plenty of opportunity for:
a. emitting "radio power" when switching;
b. being disturbed by "radio power".

You should keep your current loops as small as possible: twist your power wires together, and twist the wires to your LCD together - make them smaller if possible.
You might reduce the effect by simply protecting the "clock signal" to your LCD: add a capacitor close to the input of the clock input of the LCD (1-100nF depending on the speed).
For my customer I solved the issue in SW - otherwise he had to modify his entire production.  I solved it by:
- Ensuring that the LCD is in read mode whenever it is not written to;
- Refreshing the LCD characters and settings on a regular basis (rewrite every parameter and character every few seconds [one parameter every 20ms for example).

Prior to that I confirmed the origin of hte issue by adding filtering capacitors on the clock and on the Read/Write (but the clock was most important).