Upstream can sign or otherwise indicate integrity (e.g., Git revision checksums) of all individual source files. This ... becomes tedious to check, but can be checked against Debian sources to identify where any changes might reside. Note that this still applies only to sources rather than builds, though it's an option. It's likely not an option in wide use.
Debian also ships sources rather than builds, which can be built directly on your own systems (or within your own build-and-distribution network). Debian's had a "reproducible builds" initiative for some years (https://wiki.debian.org/ReproducibleBuilds), and this covers a fair number of packages (I don't have a count offhand), though there are notable exceptions of packages which are simply too complex to build reproducibly. I think the September 2020 summit notes are the best current overview of status, tools, and issues: https://reproducible-builds.org/reports/2020-09/
And, unlike Google Play, it's possible to download from any arbitrary Debian mirror without authentication. Authentication-prior-to-download could lead to branching logic for user-specific modified packages being delivered. Another option of course being for a generically-modified package that targets a single user or specified set of narrow criteria.
With Google the entire process is completely opaque, they do everything behind closed doors, and can hand different users different blobs on demand.
Ultimately with Google, you only have Google's word for what they're doing, and you know they have the capability to provide different versions to different users on demand of an NSL. With Debian, they have no way to attack a specific user, and you fully have the ability to "check their work."
I am curious what are good solutions to this problem? Compile your OS (and any other software) from source?
You have to rely on a distribution that has a many-eyes review policy and has security conscious users.
That's blatantly understating how many packages are reproducible.
Multiple people can grab the sources from the developer, review and apply the patches, build the package and publish the resulting hash. With reproducible builds, all people end up with the same hash, which should also be the same for the pre-built package in the repository.
In other words, instead of trusting one single person (the maintainer) you split the trust across multiple people. This is definitely an improvement thanks to reproducible builds.
And, there are large tech firms doing this already.
With the upcoming change, we loose this verification when using Google's app store.
Developers can still create key pairs themselves and upload them to Google. So they can still publish their public key if they want and you can be certain that APKs distributed from somewhere other than Play were definitely signed by the developer.
I think this is exactly the bit people don't like. I don't want them to "own" my operating system.
In the case of Apple, I agree. It doesn't make sense to use their ecosystem without trusting them fully.
However, in the case of Android / Google Play, right now the developers have the option to choose between APKs and App Bundles. Why take away that choice? If App Bundles are superior, then developers will choose that option freely. (Google Play is already really pushy when recommending to use App Bundles.)