I have a Samsungs Galaxy Gio running Android 2.3. The device has about 160 MB internal space for apps, where part of that is used by system apps. So lets say, there is about 100 MB left. During the past time, the app size somewhen increased to about 19,22 MB (22 MB with data) for a fresh install, consuming a large amount of valueable app space.
I still remember that a year or two ago, Spotify much smaller (about 5-10 MB, which is quite okay).
Can you please try to reduce the size of the app to something reasonable (e.g. 10 MB max + data) again? I would suggest putting more parts on of the app on the external SD card.
I cannot even update any apps anymore because there is no more space left and I only have very few installed :(