How long is the wiring between the sensor and the micro? If it's long (like 40cm or so) then you might want to use a shielded cable for that. And what is the time constant or cutoff frequency of that RC filter? It might be just bad component calculation. Other solution would be to implement an IIR or FIR filter inside MCU, but unfortunately I can't tell you anything more precise as I have only very basic knowledge in DSP. In fact I don't actually know if IIF or FIR is implementation is feasible using that microcontroller that you have. But that's some option to consider ()although analog filter is much much simpler to implement).
On the other hand what is your reference voltage? Do you use some kind of dedicated reference voltage source (i.e. TL431 or MCP1541), the internal reference voltage inside MCU or the supply voltage? You may want to consider some kind of amplification since LM35 signal output probably won't be higher than 1V. In that case you may amplify the signal by the factor of 4, so that you get closer to full scale of ADC. This could improve your voltage resolution.
Other factor affecting your sensor performance could be the enviornment. If it's particularly noisy one, then yoy may want to consider some kind of shielding.