The issue is what if you have to use a specific app to access some service or community. And then that app requesting access to your location data and your address book even though there is no point in it requesting either. Sure you can deny but if you do it, the app will refuse service. It can only be solved by the app store requiring that users denying access won't result in the app refusing to work, or only the features will refuse to work that actually need that data.
"just don't install the app" won't work in many, many cases.
But this doesn't really happen on Android now. Even though I can sideload apps and use different app stores, my bank never told me to get their app from Shady Store and the public transport company didn't ask me to you F-Droid. The official app store is still _the_ place you find apps in, you're just _also_ free to wander on your on.
The most famous example of an app choosing not to be on the play store is Fortnite. Google even had to add a feature to their play store search to show a message that Fortnite is not available, so that people don't get desperate and install one of the many scams. Fortnite did this because they didn't want to pay the Google tax, but other apps might do it because they want to spy on users more. The danger exists.
We can always use Apple's favorite defense on why they don't have an app store monopoly: use your browser. Facebook, Instagram, TikTok etc. all still work via the browser. I don't know a single one that doesn't (though I could be wrong)
> The issue is what if you have to use a specific app to access some service or community.
Such compulsions are the real problem. In a free society, nobody should be compelled to have a phone at all, let alone install software on one. Government services in particular should never be gated in this way. If no compulsion exists, then there is no problem with people having the choice to use any appstore they wish.
If by 'have to' you mean something along the lines of "My brother keeps badgering me to install WhatsApp" then the answer is to simply say "No." Real example. He texts me instead.
It's thankfully not mandated by governments. However, often there is social pressure to obtain a given app. E.g. when a friend group is all on snapchat and they organize outings via the group chat. Do you want to be left out of that discussion and only be informed by one person from that group who forwards the decision when and where to go to you?
In US I have not seen any government services that are available only via mobile devices. Most online government services are accessible via a website, and one can go to a public library to use a (non-mobile) computer there.
The app might be able to detect the pattern generated by the fake data generator and refuse to work in that instance. E.g. apple's approximate location feature often puts you into the city center at a very specific location. It's trivial to detect devices that are always at that precise location and only move around in discrete steps between those points.
This can lead to an arms race where the OS creates increasingly advanced/realistic fake data, and apps get increasingly sophisticated logic.
So I'm not a fan of solving this the technical way. A policy is way better, but you need to be able to enforce it.
Sure, it'll lead to arms race like you describe on one side, but let's say 99% of the apps won't even engage in that arms race if the fake data is generic enough to cause a high number of false positives (blocking someone who's not actually faking the data).
Then, we can focus on the remaining 1% of worst offenders to actually enforce the policy.
"just don't install the app" won't work in many, many cases.