Spotify should adopt the newly standardized Opus codec (IETF standard RFC6716) Its pretty much superior to all other audio codecs out there. Here is their comparison site: Comparison.
A snippet from their site:
Opus is a totally open, royalty-free, highly versatile audio codec Opus can handle a wide range of audio applications, including Voice over IP, videoconferencing, in-game chat, and even remote live music performances. It can scale from low bit-rate narrowband speech to very high quality stereo music Bit-rates from 6 kb/s to 510 kb/s Sampling rates from 8 kHz (narrowband) to 48 kHz (fullband) Frame sizes from 2.5 ms to 60 ms Support for both constant bit-rate (CBR) and variable bit-rate (VBR) Audio bandwidth from narrowband to full-band Support for speech and music Support for mono and stereo Support for up to 255 channels (multistream frames) Dynamically adjustable bitrate, audio bandwidth, and frame size Good loss robustness and packet loss concealment (PLC) Floating point and fixed-point implementation