I feel like current understanding of reproducible builds stops short of solving the problem, particularly because I don't quite see users religiously building and comparing the packages, especially hundreds of them.

A practical solution, IMO, would be several organizations running and publishing the builds—i.e. several independent F-Droids. Then, a few interested people could rather trivially automatically download the binaries and compare them. If one of the ‘stores’ gets compromised, a mismatch in binaries would indicate that.

This implies that versions should be built fully automatically from updated sources, without action on the part of the authors that is specific to the stores.

Edit: the idea of distributed builds, mentioned in the article, is similar—but IMO it's still unlikely that people will spend resources on apps that they personally don't use.