I was having a terrible time with Spotify on my Android/Samsung Galaxy S7 and S8. UI was slow, and songs would randomly stop playing for up to a few minutes and then restart. Media controls wouldn't work and sometimes the entire app would simply freeze.
Trying to isolate what the issue may be, I found that disabling "Behind the Lyrics" seems to have solved the issues. I also noticed that going Offline also helped, but this may be related to the lyrics feature not trying to pull data related to it.
I need more time, but so far, dramatically improved and feel the Spotify should further investigate this issue. Good day.