I agree, an AVcc filter would be great.
Without the filter, accuracy depends a great deal on how you power the Arduino. I did some tests with a high quality 9V power supply http://arduino.cc/forum/index.php/topic,120004.0.html.
For a perfect ADC, the maximum error is 1/2 LSB and the mean error is 1/4 LSB.
For 5V Vref and a 10-bit perfect ADC the max error is 2.44 mv and the mean error is 1.22 mv.
My result for three Uno Arduinos with the high quality power supply was max error around 4 mv and mean error 1.4 mv.
So you can get very close to 10-bit accuracy with a good grounded 9V power supply and no modifications to a Uno.
The best solution would be a filter. Good 9V supplies cost a lot and good small three prong supplies are hard to find.
ADC calibration is absolutely necessary to achieve good results. The above link describes my calibration setup.