But the regulations you are looking for should be on the device manufactures not the app stores. Require Apple to allow other app stores to be installed that has the same level of access to the OS and APIs that their native app store has, as well as direct app downloads from the internet with the same level of access (maybe with some extra hoops for security controls).

That would solve the problem. Someone will spin up a better App store. Someone already has in fact. If you jailbreak your iPhone you get access to a second app store (https://cydia-app.com) which has apps that Apple won't put in their regular store.