I just started Spotify with a stopwatch:
2:26 for the main Browse to completely render
2:42 for the live search window to give suggestions
2:52 (+10 seconds) for the search to return a result
I once thought it was because of the massive local library that had to be loaded and sorted into Spotify, but I've done away with local files to try to speed up the start up. The results on my laptop are not any better. Maybe it's because I've been updating the same client since 2012?