The App Store run by a central authority with complete control over what can even be available and the ability to modify the delivery at their own whim is certainly a big issue in terms of trusting the integrity of the apps running on a device.

If you suspect yourself to be a selected recipient (e.g. you're Edward Snowden) I reckon you should compile your own binaries. Or read 'Reflections on Trusting Trust'.

Fun fact: The App Store already serves limited edition binaries to everyone because it encrypts them per-account :)

Forget the aop store. How do we know Google, Apple, Microsoft, Ubuntu, etc doesn't give us a malicious kernel update?

I don't think we have good solutions for the problem of malicious updates in general.

The only one I can think of is a trusted hypervisor that hashes memory in the guest and reports on it. And even then, how do we trust that?