I noticed that on OSMand there's an option which lets you use online navigation, which lets you avoid using up storage space, I think this is particularly useful on a 1-time journey, either long-distance or in an area you won't visit again. You'd also be able to get real-time travel info like public transport times and the quickest routes, granted not as good as google's harvested data, but still something that could be useful.