I agree, it is difficult to find a proper alternative.
App stores do have some advantages here, today. It's also true that they don't well fit the model for open source. App stores define some root of trust for signing, but just like the CA model for HTTPS certificates, there are issues with that. App stores also bring a host of issues with user freedom. (Even the free ones can have this effect unintentionally: what percent of your coworkers know how to manage apt pinning? If one person on ubuntu 10.04 has an working, installed package, and wants to hand that exact (known working) version of it to a friend on ubuntu 12.04, can they do it?)
PGP signed binaries are one major step in the right direction. More friendly tools and popularized workflows for this would help a lot of people avoid major moments of vulnerability.
PGP (or any other signing system) also leave an interesting challenge, which is what to do in the case of key compromise. Revocation is hard. And say you want an audit log of all prior releases: what can you do?
We're all used to git having an immutable log of history by hash chaining, at this point. Is it time to start using systems like that to keep an auditable log of software releases, as well?
I've been working on something called "mdm" [1] that attempts to do an auditable, immutable chain of releases like this. It was originally designed to be a dependency manager for (arbitrary, language-agnostic, any binaries) software development needs, but I wonder if something like this is what the software distribution world needs to start evolving towards as well. Imagine if your end users could all verify that they have the same hash... and the same picture of historic releases from the same author, and the same picture of if the releaser's signing key changed, and so on.
I'd love to hear other thoughts on how hash chains and signatures can be made to intersect to tell the broadest story. The challenges are very real here.
---
[1] https://github.com/polydawn/mdm/