In any case, I think wallet users want to know when an upgrade is
available, and ability to click an 'update' button get a binary they can
trust. It's not a problem unique to bitcoind, deterministic builds are
awesome, but I don't think fully solve it.

Deterministic builds are one part of the equation. Matt Corallo actually did implement auto-updating using gitian updater:

https://github.com/bitcoin/bitcoin/pull/1453

It ran into lots of bike shedding and was eventually abandoned, but there is no question whether it is possible with the current build process.

Wladimir