Problem is that it not really is "just a store". By using the google store you get access to the google play APIs, which are upgraded separately from the device OS - which is sensible from a security perspective, but they also were created by google specifically for regaining control over what goes on on Android devices.

A lot of applications are needlessly tied to play APIs - either because that way is a bit easier, or just because google is good at marketing them, and the developer didn't think twice about it. Some relatively basic APIs are part of google play - for example maps, which needlessly is tied to google maps. Unlike Android itself the play APIs are not opensource.

Yandex tried about a decade ago to re-implement the play APIs to keep such applications working without the play store, by utilizing other services providing the same functionality, and tried to get other companies to join them. I've visited the Yandex office in Saint Petersburg a few times to discuss that back then (just checked, most of that seems to have been 2014 - that year Yandex was sponsoring my Russian visa). The effort failed for various reasons, unfortunately - the big one being that doing this required reverse engineering API changes on every play update google was pushing to stay compatible. There's the microG project around now, but it seems to be less ambitious than what Yandex was trying to do back then.

My point is, as long as at least the API for play services isn't maintained in a way that allows full open source reimplementations - or better, google releases parts as open source where we can plug different backends in - "use a different store" is not really a possible solution for many.