I dont know why the relay messes things up , but i have just made the same thing you are describing, and have a few comments,
you mention two lm335, are you reading two temps? if so , the adc needs time to recover inbetween analogue reads, i put a delay(20) and then take the analog read a second time in order to get a stable result from both my lm35 and my voltae divider,
Second,
Why use a realy to power the fan , you can just use a bigger transistor to run the fan, I have a big old mosfet that can run 50a running a pc fan, its overkill, but i pulled it from a dead charger so i dont care, if you put a flyback diode on the transistor you should be ok,
i left mine on the bench running all day with no issues,