El adc del pic y de cualquier ADC tiene un error en el bit menos significativo por el error de cuantización, por esto siempre este bit se debe descartar, pero esto la mayoría de las veces no trae problemas, por ejemplo si tu estás midiendo un valor de temperatura de 0 a 50 °C que corresponden de 0 a 5V, esto sería 0°->0V->0ADC, 50°->5V->256ADC,
entonces por el error de cuantización, (variando solo el último bit)tendrías una variación en la lectura de 0.19°. Que no se condice con el error que estás teniendo.
Lo que si te está dando problemas es el ruido.
Ahora vamos a la parte externa al pic, dices que tienes un tester midiendo la salida, los tester comunes solo miden la tensión eficaz de DC, y su respuesta en frecuencia es muy pobre. Deberías si te es posible observar la salida del sensor con un osciloscopio y también la salida del operacional, vas a ver que no es nada limpia.
Primero debes estabilizar muy bien la fuente con la que estás alimentando el pic y el lm35 como así también el operacional, toda fuente tiene riple y ese riple se propaga a todos los componentes, por lo tanto si quieres obtener una buena medición la fuente debe ser lo más estable y lo mejor filtrada posible
Ahora el tema de la ganancia del amplificador, dices que lo configuraste con una ganancia de 100 (creo que quisiste decir 10). Supongamos que el LM35 te está dando una salida de 100mv, si esta fuera estable no habría problema, pero ahora se le suma el riple de fuente más algún ruido (térmico, por RF, algún motor que se enciende cerca, etc,etc), supongamos que este ruido es de 10mV, entonces a la salida va a tener 110mV, que multiplicado por 10 tienes 110mV*10=1100mV a la salida del operacional. Ahora traducido a muestras sería 1100mV*256/5=56.32, pero como las muestras son enteras te puede dar 56 o 57 que traducido a grados es 50*56/256=10.93° o 50*57/256=11.13°, en lugar de los 10 grados.
Si ese ruido es mayor, vas a tener un mayor variación en la lectura. Por lo tanto lo mejor es filtrar bien la fuente, y si te es posible diseña el amplificador, para que filtre la salida a una frecuencia lo más baja posible.
Estás tomando muestras a una frecuencia de 1seg mas o menos, y además la mayoría de los sistemas varían su temperatura muy lentamente, así que colocar un filtro a la entrada no va a dañar demasiado las lecturas. En caso de no poder diseñar el filtro con el amplificador, haz como te han aconsejado y coloca un filtro RC a la entrada del ADC de la frecuencia de corte lo más baja posible.
Espero no haber arruinado la explicación con tantas vueltas, Saludos