I used to be in the same boat, mostly due to Spotify's recommendation algorithm. Unfortunately they've since removed all ways of giving it feedback about what I like, and now it just recommends the same few songs over and over and over.

Might have to go back to downloading, at least playback will be more reliable.