arduino can use a reference voltage of Vref=1.1V (lower than 1V is no good idea, IIRC)...
@10bit and a sample rate of 5kS/sec u get about 1mV/LSB...
a LM35 delivers 10mV/K...
many arduinos can neither do differential ADC nor gain (e. g. the ATmega168 cant)...
the ATtiny25 can do differential ADC and can use a gain of appr. 20x...
that means, that u can get about 50uV resolution and that is 0.005K... 
the Arduino Due has a
"16-channel 12-bit 1Msps ADC with differential input mode and programmable gain stage",
that could do the same as (or better than) the ATtiny25...
the Arduino Mega 2560 can do the same as (or better than) the ATtiny25...
i forgot to mention:
- oversampling might increase the resolution by some bit(s)...
- if u use a thermocouple u might need some external circuitry (like one differential amplifier for each thermocouple...)...