Por muy precisa que sea tu conversión ADC, así tengas 16 bits reales de precisión, el LM35 especifica en su hoja de datos que es confiable a intervalos de medio grado, de manera que desde 0° hasta 100° no tendrás más que 200 valores diferentes, muy por debajo de los 1023 valores de un ADC de 10 bits; en teoría un ADC de 8 bits tendría un trabajo cómodo con un LM35.
Si requieres más precisión te recomiendo cambiar de sensor.