It turns out that the achievable performance is even a bit better than I thought.
As per the program examples provided within the Arduino IDE, I have allowed a 1 mS delay between analog reads, supposedly to allow the ADC readings to stabilize.
However, in fact the averaged voltage reading seems to be just as stable and noise free if this delay is removed.
This is good news. In one of my applications that requires averaged readings only every 0.5 seconds, it means that the number of samples in each average can be increased from 500 up to around 5000, even further reducing the fluctuation between successive averaged readings, and thus the ability to detect very small changes. A change of 1 part in 100,000 of full scale is now easily detectable.
In another application, I will keep the 500 samples per average, but can now update the averaged reading at 10 Hz rather than 2Hz, fast enough to put inside a high-performance PID temperature control loop. This system is already operating in an all-analog implementation, and easily controls to 0.001K, but being able to do this in an all-digital implementation has many advantages.
Who would have believed that a lowly Arduino UNO could do that? Actually, it can't do the precision PID because it has no DAC, but I have a Due sitting here that does have a proper DAC (actually 2 DACs), so I'll use that instead. Unfortunately the DACs are only 12 bit which is not enough, so next challenge will be to significantly improve the Due DAC resolution, which I believe can be done. A bit of noise and drift in the upgraded DAC won't matter, because it is within the control loop.
I'm having a lot of fun making Arduino boards do things they were never meant to do.
A final note of caution. The dithered and averaged analog input performance I have described was done with an Arduino UNO or, more precisely, a Freetronics 11. It is possible that other Arduino boards may be inherently noiser, and not work as well. For example, I am finding that the ADC on the Due is very noisy, to the point that despite being 12-bits, it actually performs more poorly than the humble 10-bit Uno. Those extra 2 bits are buried in the noise. On the one hand that removes the need for external dithering, but because the said noise is unpredictable and large, the average reading fluctuates more than with my dithered Uno, and it seems to drift more as well. It should scrub up OK, but I'm a bit disappointed with the ADC in the Due board.