The actual issue you are seeing on the LCD is usually caused by the LCD and the host (the arduino) getting out of nibble sync with each other. This is what causes the garbage on the screen. The LCD is using bytes that are 4 bits from one byte and 4 bits from the next byte. So garbage shows up. Once this happens the only way to get back in sync is using a special initialization procedure which the LCD library uses when begin() or init() is called.
This loss of nibble since occurs when there is an untended pulse on the E signal on the LCD or if the LCD fails to "see" the E signal transition properly.
Either of these can happen where there are power issues. Power issues like glitches can cause the LCD supply voltage to drop too low or spike, noise on the LCD supply voltage, or momentary voltage differences between various components connecting to the LCD. When there are voltage issues, the LCD can potentially "see" phantom E signal transitions or miss actual E signal transitions.
All these kinds of things can happen when relays are are used and are switching loads if the circuitry does not properly isolate power and/or the control signals.
I didn't fully understand your situation, but it sounds like you are not only using relays but are also switching some mains power which could be large loads.
These are the kinds of things that can create power issues for power supplies which then creates power/voltage issues for the Arduino its circuitry and the LCD device.
Can you fully explain what is happing again. I didn't understand it. It sounded like the mains power was being turned on/off or switched over which I'm guessing also includes the power to Arduino?
--- bill