Another +1 for Google Music. I subscribe to Google Play Music All Access. Anything that isn't in the library, I'll upload from my computer. I keep all my playlists on my device.
I switched from Spotify when it Google Play Music All Access first came out. Unlike Spotify, which limits you to 3,333 tracks stored offline, you can store as much music as you can fit on your device. If I store all my playlists on my device I've got something like 50GB of music.