I have the same issue as everyone else here. Using Pixel 9, I've tried a lot of different configurations to no avail, no downloaded maps (and actively prohibited downloaded maps). I do use Android Auto but no location sharing.
A bit more context about the issue (as I've encountered it). The default map layer is pretty much gone, I start seeing things if I move around on the map but that doesn't trigger a full reload. Switching the type from "Default" to "Satellite" or "Terrain" loads the visual map in the respective type but the places on the map are still missing. So the nearby building that are typically labeled won't have any labels. Even if I do a search, the results show up in a list but not on the map. However, if I click on a specific location in the list or lookup a specific place, it does get selected. The same issue also happens on Android Auto (in the Google Map of my car's console), I end up switching to satelite mode to be able to keep navigating.
Clearing cashe alone does not solve the issue but clearing storage does. Fortunately, it's not a huge hassle, but it is annoying, especially if you have any settings that you want to be maintained.