I had thought about doing something similar to this, temperature data logger for each room in the house to control heat vents and hopefully save some money.
The analog approach is less expensive, but prone to environmental effects. If you stay with the LM35, I would recommend shielded cable and ferrite beads on the power and ground leads. This is a DC circuit and the signal won't change rapidly. If you think your getting any EMI on the signal line, you might try a very small bypass capacitor. You could also do 3 or 4 samples from the LM35 and average them:
sample1 + sample2 + sample3 ... / number_of_samples.
This would give you some level of accuracy even in an electrically noisy environment.
At $5.70USD a pop (digikey), the DS18S20 could be justified if you don't need many sensors. This is a pure digital sensor in a TO-92 case, and would be my preferred choice. You would only need one sample from the device, has wide temp range, and .5C accuracy in the intended range. The up side... you don't need to change your circuit layout, the TO-92 would drop right in and connect to the controller via one wire. They can also be daisy chained on the same wire. The down side is the code for your controller just got exponentially more complex as you would have to addr/read/write over one wire.
Check the datasheet at maxim-ic.com
--Ooz