I have the same problem when trying to run Spotify on my iPod Touch. Even though it's a 5th gen device wth 64 GB of memory (the maximum available), after doing other activities, e.g. web browsing, then running Spotify, it usually takes around 30 seconds for the Spotify start screen to disappear. Removing and reinstalling the Spotify app did not help.
I do have a workaround though: if I want to start listening to music right away without the 30-second wait, I run the Pandora app instead; that app only takes 3 or 4 seconds to start playing music.
The Spotify app did not used to be like this when I started using it a few years back, but after one of their "updates", I don't remember exacly which one, it was starting up much, much slower than before.