Кроме Яндекса есть карты OpenStreetMap, для Андроида их использует софтина Maps.me, но она платная, бесплатный упрощенный вариант Organic Maps. Ну и известный Навител, но он скорее для сельской местности, там у него покрытие будет лучше чем у Яндекса.