[Garcia98]

Providing a checksum along with the binary singlehandedly solves your concerns, and you can add gpg signatures if you want.

[pmoriarty]

A checksum can be falsified as easily as a binary, and so can a signature. Only if you participate in a web or trust are you theoretically better off... but most people don't, so all such measures do is give a false sense of security.