If you enjoyed Musicovery, you’ll probably enjoy Deezer as well. You can’t download the files, but it will stream and… It’s Legal!!!!! It was created in France and has evidentially come to an agreement with copyright holders. Read more about this on their press release.
Enjoy the music!