Ok, some development advice for you.
1. When I start the app, the first thing you must do at all times is present me with a usable UI. This should happen within seconds. That means 2 or 3 not 45.
2. When I stop the app that means stop. Not continue running and doing stuff anyway. It means "I don't want to run Spotify now and don't want it to use my memory or CPU". Don't keep a "service" running. Just stop.
3. When I start playback of a playlist that has been downloaded, just play it. And keep its place. Play it without interruption. The only thing you need to do possibly is load the next song.
4. When I hit pause or stop, stop right away.
5. The app is loaded into the SD card, in a persistent state. That is where it should be. Use SQLite or your own setup if that is better. But it's primary state should be persisted. Load things when you need them, put them back there when you don't. Of course with automated garbage collection it's always a problem. A shame poor programmers can't manage resources properly that you all need them so badly.
6. Loading from persistent cache into memory is slow, yes. That however is exactly why you should not be doing it all at once when the app starts. Because it's slow and it isn't what the user asked. Loading a small amount as you need it is not slow. Not slow enough anyway. Remember that most of the time the user is just listening to a song and wants to hear that song play smoothly without interruption. At other times the user is interacting and UI is always slower even than disk access.
7. Communication between the persisted state and the server (the "cloud")) should be transactional and in diffs. When you start, you need to send the server a message about your current state and then get updates which are diffs between the state you have and the current one. At times it may mean reload all but most of the time it won't.
Note: I'm now in my 3rd song again, I have been trying to listen for nearly an hour, I have not yet had a single song play from start to finish without stop-start-stop-start and restarted the first 3 in hope of hearing them smoothly but failed to do so. I should have got through 12 songs or so in this time.
I'm trying to get work done that I'm being paid for (a lot higher quality than your **bleep**. And people pay a lot more money for it too. You think you're big, sorry you're not as big as where I work). The music is supposed to be playing in the background but it's continual stop-start **bleep** is causing me so much distress and distraction.