Мне кажется, вы путаете карты и сами программы.
В случае с "гуглокартами", про которые идет речь, сами карты идут в комплекте с приложением гугла, которое их рендерит на телефоне, и серверным сервисом, который делает навигацию. Я сомневаюсь, что существует (широко распространено) другое ПО, которое работает с картами гугла (это бы нарушало лицензионное соглашение гугла). Поэтому в случае с гуглокартами нет никакого практического смысла рассматривать эти компоненты продукта отдельно.
Что значит "Гугловские быстрее на телефоне"? Что они делают быстрее?
Я думаю, речь идет о рендеринге (отображении) карты на устройстве.
Например, у ПО OsmAnd, которое работает (в том числе) с osm-картами - фантастически медленный рендеринг. Это может быть незаметно на топовых устройствах, но на скромных девайсах при насыщенной подробностями карте просто видно, как на экране появляются слой за слоем.
Есть и другое ПО, которое работает с osm-картами: например, maps.me. Оно рендерит быстрее.
Маршрут обычно строится за секунды в любой навигационной программе при любых картах.
Во-первых, он зачастую строится не в навигационной программе, а на сервере (например, так у гугла, яндекса). Это обусловлено многими причинами. В том числе и тем, что у этих программ на оконечном устройстве - растровые карты, а векторные (по коротым возможно строить маршрут) - только на сервере. (Это же, кстати, объясняет, почему у них такое быстрое отображение карт - растровые карты практически не требуют содержательной обработки перед отображением)
Во-вторых, например, OsmAnd на подробной карте маршрут на 500км может строить несколько минут (и иногда в итоге его вообще не построить), так что приходится строить его не сразу до конечной точки, а кусками. Так бывает, когда навигационные задачи берутся решать люди, которые ничего не понимают в теории графов.