I have a standard 16×2 LCD display (I believe it is Hitachi HD44780 compatible – see summary and specification below), hooked to an Arduino Uno using 4 data pins, as described here, though I've added 2x 220ohm resisters in parallel (ie a 110ohm resistor) on pin 16 (Backlight ground), and replaced the Pot with static resistors to create 4V on Vo.
In short, RW is wired to ground, and RS, Enable, and Data4-7 are connected to Arduino pins, while Data 0-3 are floating.
I have other things (sensors, a transistor with an optoisolated SSR and a mains relay, some buttons) connected to different pins on the Arduino. The code I use writes text to the display a number of times a second, and normally, the display works perfectly.
However, when the relay closes (it takes about 10ma, and is controlled by a transistor which is in turn controlled from one of the Arduino pins), sometimes the LCD becomes garbled. It remains garbled usually until the relay next closes, but sometimes when the relay opens, or after a few more cycles of open/close to reset. The garbling always starts and stops at the same time as the relay either opens or closes.
By "garbled", I mean that every time I write to it following it becoming garbled, rather than writing english characters, I get a string of characters, that I usually cannot identify in the datasheet (though some I can). This string of garbled characters tends to move left along the screen as I write new text to the LCD.
I am confident it's not the Arduino itself getting confused, as I write the same text to the Serial monitor at the same time, and it is not garbled.
I've since experimented with wiring the RW pin to an Arduino output, and Data0-3 to ground, but this doesn't help. I've powered the whole device with a 9V battery or with USB, and it doesn't help. I've replaced the battery… no change.
The only thing that seems to work is having no load plugged in to the relay, but that defeats the purpose 🙂
I don't have a signal analyser or anything more sophisticated than a multimeter, a laptop and an arduino… Does anyone have any hints for helping me debug this?
LCD Summary Sheet: http://oomlout.com/LCDD/LCDD-SUMM-BC1602A.pdf
LCD Specification: http://oomlout.com/LCDD/LCDD-DATA-BC1602A.pdf
Example of garbled text: 
Best Answer
Do you have a diode across your relay? If not the inductive spikes on closing/opening will likely cause problems.
When you e.g. stop the current flowing through a relay, it tries to keep it going, if there is no route of discharge it will create a large voltage (essentially it will keep rising until it finds a route).
Specifically the formula is V = L(dI/dT). This means the inductor opposes changes in current through it by developing a voltage across it proportional to the rate of change of current.
Try placing a diode across the relay, orientated to oppose normal current flow.
EDIT - checking the product page it seems it is a "ready rolled" relay in a box with peripheral components added, so it's unlikely to be the above. Even so I would try placing the diode across the power to the relay.
Also make sure your supply is well filtered as mentioned in the comments. Place a few capacitors of at least 1uF next to the ICs and LCD, and a bulk cap of >100uF somewhere (all from power to ground)