Может быть без интернета долгое время занимает холодный старт GPS? Бывает нужно подождать несколько минут пока он раздуплится. Посмотри что показывает приложение Gps status & toolbox или аналогичное, работает ли геолокация, все ли спутники видит? Не буду просить скрины скинуть, но ты смотри чтобы там все зелененьким горело, ну разберешься короче.
Если в телефоне есть GPS/глонасс/аналог, и устройство видит спутники, яндекс.карты точно должны показывать локацию безо всякого интернета.
Возможно еще что у тебя лютый китайский телефон без GPS.