I'd recommend trialling Deezer out. In Australia, it is slightly cheaper than Spotify, pushes higher quality songs, boasts a library of around ~75,000,000 songs, separation of songs/podcasts.

e: Nearly forgot - Easy to upload custom songs/albums. They aren't organised the best (On phone, they are all stored in 1 playlist called My MP3s) but they're there!