I've discovered the same thing, if doing analogReads, you need a decent PS, otherwise the noise puts the readings all over the place. Even then, I still have to do quite a bit of filtering/smoothing in sw to get stable and reliable readings.
An unscientific observation is that the old-style linear supplies may be quieter than the newer, more efficient switched-mode supplies. This is from just doing some trial and error with existing supplies I've had laying about. I wish I could identify a good, cheap supply for these applications. Perhaps the inductor is the next thing to try.