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.