Like you I'm very frustrated by how little choice we are being given in the matter, but you have to admit that SOME (perhaps very few) applications that collect our data have been amazingly useful. Mostly they have been made by Google; Search and Maps. Could they have made these and distributed them for "free" without tracking? Probably not. What I would like is to be able to opt out, and instead pay for the app. I wonder, though, how expensive would Maps really be if we all had to pay for it instead of being tracked and advertised to? I think I have a lot more to say on the subject, but I'll keep it short for now.
I actually think Google could still afford Maps. Look at OpenStreetMap, for instance: https://www.openstreetmap.org/ They could definitely afford search by targeting terms alone. DuckDuckGo does it.
DuckDuckGo is alright, but I haven't used it much so I can't speak for its quality. OpenStreetMap seems decent enough, at least for just finding your way, but what about all the other things Google Maps is great at? - Traffic estimation (could NOT be done without tracking) - Searching for non-specifics such as "restaurant" - Street View; this one is particularly extravagant, in that they needed to drive across the whole world. It's not the MOST useful feature on Maps, but it IS useful on many occasions, and you need a lot of money to do it. Yeah, I lived before Google Maps, and it was alright. I could usually find a place to eat or drink, and I could find my way by asking people. But undeniably, I have found a lot more "obscure" and good (thanks, reviews) places, especially while travelling, with Google Maps. It's saved me a lot of time stuck in traffic, and it's often quite good at knowing when a road or train line is closed. Tens of hours of my life have been saved, I'm sure. My point isn't simply about whether it's possible to do these things without tracking; the question is also if it's feasible to do on a modest budget.