Какие есть варианты (лучше бесплатные) выставить RDP наружу так, чтобы защитить от взлома?

Хороший повод приобщиться)
Если знакомы с облаками можно очень за недорого поднять микротик в облаке и настроить редирект на свой RDP. На штатном файрволе RDP разрешить подключаться только с IP адреса микротика. Но нужны все же навыки работы в IT выше средних. Для домашнего пользователя все это сложновато (((

Как совершенно посторонний провайдер может не пустить в интернет?

Поддержу коллегу в его предположении. Но поскольку вы говорите что оборудование менялось, а трабл только с телефоном или планшетом, посмотрите какие днс получают они. В крайнем случае пропишите свои. Вообще давно практикую не использовать днс сервера провайдера. Прописываю всегда 1.1.1.1 и 8.8.8.8. Ушлый провайдер ваши запросы и так на себя завернет.