Google Music's "I'm feeling lucky" is awesome. This is very subjective, but I feel it makes much better predictions as to what I'll like than Spotify. Maybe someone else has a different experience?
It's all gone down hill since they switched everything to mood-based radios. I feel like the main problem is that I like to listen to albums and Google seems to assume I only want to listen to random streams of disconnected singles. I seem to just get played the same stuff over and over, too.
I don't know how to find new (new to me, not the world) music anymore. Are there any good services that anyone recommends?
I have the same problem. Usually I find new stuff on the various music subreddits and last.fm's Similar Artists page. Even though I have tons of playlists and saved songs on Spotify, their recommendations usually suck (probably because I listen to just about every music genre under the sun.)
Their radio feature rehashes the same songs I've heard dozens of times, and Discover Weekly is usually so awful I never listen to it.