eles respondem
Eu uso o Sound Cloud, mas é uma rede social com foco em artistas independentes, muitas músicas famosas e que não são independentes são dificeis de se encontrar nela. Pra quem gosta de bandas independentes, artistas de rap ou trap e eletrônicas é uma boa escolha.
Mas ele faz o armazenamento de música por cache, uma vez que você reproduz a música dá pra você ouvir ela sem internet, isso se você não limpar o cache do app com frequência.
E é grátis
Foobar2000. Inclusive é o melhor player para PC, também, pelo ínfimo uso de memória e alta capacidade de customização.
Mas obviamente minha sugestão se refere ao Android. E você terá de baixar as músicas de alguma forma, seja ripando do YouTube ou de outros locais.
Spotify e Apple Music são os melhores (sim, funciona pra Android)
Spotify (baixando no premium) é o SoundCloud (mas não vai ter tudo que você quer, é bom pra descobrir coisa nova). Também pode baixar no pc e e jogar pro celular, daí cê ouve em qualquer player e tá tudo certo.
Spotify.. deve tá uns 15 reais por mês na versão Premium