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.