I'd also suggest trying Google Music. I moved to it originally simply because I could upload my existing music collection to it, and listen to it wherever. Then Google gave me 3 free months of the subscription service - and I'm seriously considering paying for it once that's up.

It runs in a web browser on Linux just fine - and I find a lot of their suggested artists/tracks are closer to my tastes than I got from Spotify.