I had lot of issues with Spotify on my previous phone - but it was old.
Now I recently bought a brand new, top tier smartphone (Sony Xperia XZ), and yet I face the same issues.
When I start the process Spotify, all is fine, I start my playlist then I lock my phone or switch to some other app. But when I decide to go back to Spotify some time later, it feels like I am running it on a minitel: searching a song yields no result, when going to the songs tab it pretends to load for ages (even though they are all stored offline), when I want to make a playlist and press "create" it just freezes for at least a minute...Actually I think there isn't a single part of the app running correctly at this point, and I have to kill the app a couple times to make it run again as a fresh process, even though I've read doing so is damaging Android over time. Once, my phone even ended up restarting on its own when I returned to Spotify, that should tell you how much it's sluggish. Yes, it actually makes the whole system slow down, not just the app: when it occurs I feel like Harrisson Ford who did a wrong move and is now trying to escape a temple before it collapses, so I press the home icon, but it still takes at least 30s to take me back to home screen.
I suspect that when Spotify is relegated as a background process, it thinks "oh okay I can go to sleep now", and when I go back to it after a while it has a hangover. This is not normal in 2016, and considering I have to pay full price since the student discount is not available in my country, I will not hide that my frustration is becoming bigger and bigger. I didn't complain too much with the issues on my previous phone, but I expect a perfect service on a brand-new, powerful phone.
I use the latest nougat android OS, and the latest Spotify version. The problem was already there when I first bought the phone, running marshmallow at the time.