I have found that one feature that is severely lacking from the Spotify mobile app is a "Recently Played" list. I would simply want a text based list of the last, 25(?) songs I have listened to, available from most navigation screens. This way, instead of hoping my search terms are saved, or always remembering to add to stars (sometimes I don't want to star a certain track) I can find it quickly and easily.
Second, I would love for an artist to have a "Top Hits" tab/list/section. My scenario: A friend mentions that there is a great band I should listen to. When I search for them, I find two standard (Non-hits) based albums. I now have no idea what songs to pick to try out. On other apps (Rhapsody) the "All Songs" would have songs sorted by popularity. Even for bands I am familiar with, this feature would be helpful for quickly choosing a song is very popular.
Spotify mobile is a great app, but certainly has a lot of room to grow.