Сначала пишеться на том языке который вы знаете, а дальше уже если приложение "взлетело" смотрите во что упираетесь(ресурсы/возможности языка) и либо улучшаете свой код, либо переписываете на языке больше подходящем под задачи, либо переезжаете на железо мощнее.
В 99% случаев взаимодействие клиента и сервера реализуют используя стандартные протоколы(http(s), WebSocket protobuf итд), библиотеки для работы с ними есть во всех популярных языках.
Ну и раз вы писали сайты то должны понимать что фронтенд сайта это по сути клиент к серверной части и его запросто можно заменить хоть мобильным, хоть десктопным клиентом без изменений серверного кода. Конечно сам серверный код должен предоставлять API, а не быть лапшой из пхп+хтмл.
Что же касается хостинга - для старта подойдет любой, даже shared. Но лучше сразу брать vpsку, например у Aruba за 1евро, у OVH за 3евро или у DigitalOcean за 5$. А на время разработки можно воспользоваться бесплатными тарифными планами от Amazon/Google/Microsoft.