Distortion in ADC output
It looks like the Galileo uses the 5 V power supply as the reference voltage for its ADC (see p. 18 of the schematic).

When you close your relay, the extra current draw is causing your 5 V supply voltage to droop by 0.4% according to your measurement. 

1 count of an 8-bit ADC is 0.39%. (The ADC is actually a 10-bit part, but maybe the software interface is throwing away two LSBs to give you an 8-bit reading)

It looks like the voltage droop is also affecting the ADC reference, and causing 0.4% error in all ADC measurements.

To fix this, figure out where the power droop is coming from and improve that part. It could mean getting a new wall wart, or it could just mean using thicker (or shorter) wires somewhere in your system. Or it could mean using separate power supplies for the Galileo board and the relays.