For real time navigation, Waze type solution could work -- aggregation of real time data from users. Also, smart city projects have open traffic data APIs, although not sure wether there is something properly real time, or it something like hourly aggregates.
So that would be still a giant project, but data does not seem to be the bottleneck.
This seems like exactly the kind of thing that users who opt specifically for a privacy conscious OS are not going to readily share
Secondly, and this is really a different issue and perhaps not that widespread, I don't like turning on location on my devices simply because it reduces battery life. It's not a privacy issue but it's another roadblock (pun not intended) to gathering navigation data
The main thing an OS like this needs is the a ability for it's users to run their own "cloud" infrastructure and attach that to their own phone.
Company can offer this as a SAAS service paid, providing they to proper end to end encryption and are not able to read the data they store. Also a good way to fund future development.
"Duval’s team made use of LineageOS ... [which] doesn’t ship with any Google apps ... To counter that, Eelo will come preloaded with a handful of services you would need out of the box such as an email client, a productivity suite for accessing documents, spreadsheets, a search engine that won’t track its users, and more. The one application which is being a bottleneck for Eelo’s potential success is navigation ...
Eelo will have a repository of both open-source as well as other Android apps. To ensure users don’t install one of the latter and ruin the purpose of using a privacy-focused operating system, each app in Eelo’s store will have a security score. Through that users can be more informed about how well a particular app treats personal data and based on that, decide whether they’d want to install it."