Хочу сразу сказать, что при помощи last.fm музыку нельзя скачивать - ее можно только слушать. Но у этого ресурса есть, конечно, свои достоинства, но речь не об этом.
Лично я уже четыре года пользуюсь шведским ресурсом Spotify. Ресурс существует как в вэб-форме (play.spotify.com), так и в виде приложений для android, ios, windows (которое удобно более чем полностью). В базе более 23 миллионов треков. У каждого исполнителя есть страница, на которой все песни распределены по альбомам, так же есть список самых популярных песен исполнителя и похожих исполнителей. Сервис бесплатный, однако есть подписка, которая позволяет прослушивать песни в более высоком качестве (320 kbps) и сохранять их для прослушивания оффлайн. Одно но - сайт на данный момент не функционирует в России. Но ничто не запрещает обходить это условие через ну скажем сторонний vpn (думаю, разберетесь при желании). Переходить ни на какой другой ресурс не вижу смысла, потому что база невероятно обширная, настолько, что в ней имеются некоторые песни, которых нет в базе вконтакте. Причем в базе содержится и большинство русских исполнителей. Да и достаточно посмотреть на оценки и количество скачиваний в том же google play, чтобы убедиться, что ресурс - более чем достойная замена вконтакте. Да, совсем забыл сказать, что по каждой песне либо по любому самостоятельно составленному плейлисту можно подобрать плейлист похожих композиций - то же самое выполняет кнопка "показать похожие" вконтакте.
Так же есть ресурс Deezer, который тоже бесплатен. Существует в качестве сайта и приложения для android и ios, проблем с доступом в России никаких нет. Функционал такой же, как у Spotify, однако база поменьше.
Если сравнивать вконтакте и Spotify, то отдаю предпочтения полностью второму ресурсу из-за объема музыкальной базы.
Spotify. Теперь он доступен в России, можете спокойно зарегистрироваться и забыть про Вк и его рекламу. Предупреждая вопрос, перенести записи и плейлисты не получится. Только заново создать.