Was having the same issue of wildly swinging values reading TMP36 from A4. Fixed it with a 0.1uF cap.
See before and after images for data collected at A4 attached to TMP36. “Before” is without a 0.1uF cap from A4 to GND - values swinging wildly in a range of 19c to 27c. With a cap everything smooths out. The “before” picture reminds me of line noise seen on my scope, a common issue when building stuff on a breadboard.
Images posted on imgur HERE.
Moral of the story (for my problems at least) - add a cap, as suggested by BDub.