Arduino Uno - Analog Input: Random power readings.

Yes and lookup pull-downs too.... Most handy to be able to 'preset' inputs to known states... which is what it is all about, that and understanding when it is necessary and when not... A 'hint', better safe then sorry as you found out... start with 100 K and go as low as necessary to keep the open pin quiet or not reporting change that isn't there...

Bob