I mean placing your phone in one of those car holders or having someone else hold it. It may not be entirely as convenient as having it displayed on a built-in screen, but it's Google-free and works. I don't think there are any full software alternatives, because to my knowledge, the car has to allow apps to access the monitor, so you can't just have any app there. Whatever other things Android Auto does, you should be able to do with just your phone.
I guess the alternative is to get something to hold your phone in place.
It's not a 100% solution, but many head units will have hdmi input, but you might have to accidentally install the head unit in a way that bypasses the parking brake interlock for it to work while driving. Most phones can utilize a USB-C to hdmi adapter for screen mirroring, although touch data won't be sent to the phone.
Even car sat nav is an iffy subject. If you car has a data connection, there's good odds that someone is harvesting that data.
For example, I've heard GMC happily sells OnStar data to the lowest bidder - it comes anonymized and aggregated but it's hard to believe they aren't collecting it in a less anonymous fashion.
I keep a GPS in my car in case of emergency, but I try to plan my trips ahead by memorising landmarks on OSM. As a species, we are losing our navigation skills.
I think your best bet would be to get either a head unit that has full android on it or an Android tablet and then side loading the apps you would like to use
I'm sure it's still possible on certain cars, but they're getting harder and harder to find as more and more companies move from the standardized head unit sizes and over to the tablet-style interfaces.
If you want an integrated setup you can either roll your own in car computer or use the apple stuff.
If you can tolerate the 90s style system then a secondhand gps (do your research) and an mp3 player connected to your stereo and the little clip that holds your phone in front of the vent works.