> But if every company, publisher, developer may host their own, including their own OpenPlay Services, how do you tell what is a trustworthy source?
This is exactly the situation you have now with Android: anyone can install an APK from anywhere if they want to.
As far as establishing trustworthy sources, I would imagine this would work a lot like using Apt on debian. You could have a trusted package manager where there is some vetting process for getting listed, and you would trust the community to identify and report malicious packages quickly.
Also unlike the app store or google play, you'd likely be running mostly open source software you can inspect yourself if you want to make sure it's safe.