N advantage in using 8-bit mode in 16×2 LCD displays

Oh, duh, I didn't read your code carefully -- your send SendLcdByte is wrong:

    void SendLcdByte( unsigned char command_0_or_data_1, unsigned char command)
{
    SendLcdUpperNibble( command_0_or_data_1, command);
    // send the lower nibble next
 // AS WRITTEN:
    P1OUT = (command & 0x0F) | (P1OUT & 0xF0);
 // SHOULD BE:
    P1OUT = ((command & 0x0F) << 4) | (P1OUT & 0xF0);
    Strobe( command_0_or_data_1);
}

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)