I don't think this is a fair assessment of Spotify. I discover new music all the time through Spotify, here's what I do.
Choose a song, artist or playlist that you really enjoy, right click and select "Go to _______ radio". Spotify will instantly generate a whole new playlist for you based on the selected song/artist/playlist.
I've spent hours discovering new music this way, good luck.