adry-kona, lamento decirte que el único que me suena con esa descripción seria el Spotify, y es de pago...
Aunque algo mas simple, hay un programa que te permite escoger para escuchar radio online basándose en el servicio de radio Shoutcast, y tienes radios de todos los tipos, no solo los generales (Pop, Rock, Disco) sino que también mas específicos (Piano Jazz, Clasical Jazz o mi favorita: Smooth Jazz). No es de canciones, pero si podrás escuchar todas las del mismo género.
Se llama
XiiaLive, también tiene una versión lite pero aqui tienes el .apk de la full si te interesa.
http://www.megaupload.com/?d=2GAFCOD1