The problem is they don't allow apps to come from anywhere else, this is the core of the issue and what everything eventually comes down to.
Make it possible for users to control their own app installation sources on the hardware they own, show them what is happening when they do so, that they are replacing Apple as the source of trust with the developers of the app marketplace or app they are installing, but only do it once, it can't become a nag.
If they do that, then whenever anyone complains about App Store rules Apple can just tell them to do everything themselves instead, no APNS, no convenient installation from a pre-installed App Store, no seal of approval from a partner the user trusts, no free hosting, no infrastructure for app updates, etc.