Idk if it's still the case, but amazon used to have WAY fewer songs than Google.
With Google, you can create custom playlists. Its "smart" playlists are actually really good imo.
You can then tell it to download any given playlist for offline playback. Currently, I have mine set to download any new "thumbs up" tracks whenever I'm on WiFi. That way, if I'm low on data or out of service area, I've still got a bunch of songs I know I like.
May have to tweak that with the 6P though, because I've got like 10GB on my Note's sd card right now.
Of course, I'm good to go with room with 32GB onboard & a 32GB card though, so 64 onboard should be fine.