Electronic – Extra pins on HD44780 lcd

I changed my initialization code so that it sent the upper 4-bit nibble of the function set command twice. Following which I resent the upper 4-bit nibble followed by the lower 4-bit nibble. This does not match the datasheet which seems to indicate that you can send the upper 4-bit nibble then send the function set command upper 4-bit followed by lower 4-bit.

// Works sometimes pseudo-code
port=0x20;
e=1; e=0;
port=0x20;
e=1; e=0;
port=0xC0;
e=1; e=0;

// Works all the time pseudo-code
port=0x20;
e=1; e=0;
e=1; e=0;
port=0x20;
e=1; e=0;
port=0xC0;
e=1; e=0;

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)