Switching relay on and off affects analog sensor output voltage
There is only one, common ground plane, connected to power supply's
  ground wire.


This is where your problem is, very likely: a common ground between high-power signal path (inductive relay and 3-A heater), and a sensitive sensor which output is referenced to common ground. The effect frequently happens when power and signal ground are shared and routed improperly. This is called "ground bounce". It is not that the signal changes by 10-20 mV, it is the shift in ground potential between the sensor and MCU due to return current flowing form power part of the design.

To avoid parasitic interference of high-current into sensor readings, the grounding should be done as something along the following lines:



The following ground routing is bad: the MCU will read the actual Vout (which is the true value relative to sensor IC ground) plus the parasitic voltage drop along the power plane.