> the walled gardens are clearly a market failure
I wouldn't call it a market failure, there's plenty of benefits with wall gardens and it's not done solely for profit. BUT there's also drawbacks and places where walls don't make sense.
Not being able to install arbitrary apps from various app stores provides security, UX consistency, and stability of the software. But there's also drawbacks for things like privacy or abusive censorship or copyright policies.
Given the benefits/drawbacks, the best solution is to have options in the marketplace. If you prefer having more control, don't mind sacrificing deep horizontal product integration, or doing the leg work to make it ideal (doesn't need to always 'just work' predictably), etc, then you should have the option to use an OS/device that offers that.
Personally I'd rather see Google make Android more flexible (for ex: making Google Play Services less restrictive) rather than forcing every OS to be like Android.
But I'm not sure how that could be done via restrictive policy without throwing the baby out with the bath water (other than targeting monopolistic behavior like preventing choice in browsers). Otherwise taking a more-freedom approach would be best, maybe by investing in open platforms, investing in public relations campaigns to make people understand why lack of choice is bad or a consumer-friendly 'open platform' label to guide shoppers, incentives like small tax breaks for offering more open platforms, etc.
For Apple, they could offer a stripped down iOS (like a server edition of a desktop) without all of the services and side-loading restrictions, without having to ditch the current approach that people like.