Amazon Music seems to be pretty good as far as quality is concerned. I think they download the MP3s onto the phone's local storage so they don't have bandwidth issues? Either way, I could hear the difference between Spotify and Amazon music. The difference between Amazon music and my own MP3s was not as apparent.
Pandora seems to sound "fine", although I seldom play it loud enough to notice. Spotify was the only one where I noticed the quality being notably bad. It's possible it's due to a low bandwidth fallback. And maybe they throttle their own servers at peak times, in addition to detecting the lack of local wi-fi.
When I last moved, I plugged my phone (running Spotify) into my receiver to check that I'd gotten my speakers set up right. It was so muffled-sounding that I was worried I'd somehow damaged my speakers!