Я клементиной пользуюсь уже давно - идеальный плеер для меня. Даже на виндовом компе он заменил фубар.
С кодировками проблем нет, поскольку я в тегах принципиально ничего кроме юникода не использую - национальные кодировки не нужны.
Про BT не знаю, но есть приложение удалённого управления для онройда. Думаю, вывод можно огранизовать на уровне системы через пульс.
Всякие сервисы поддерживаются, в т.ч. VK. Яндекс врядли, у них же никакого API для сторонних клиентов нет и люди какие-то костыли городят.