Bitcoin offers a neat solution for public key verification. I'm about to use that in a Bitcoin-related service that I'm about to launch. Here's an explanation from the security page:

    #### Public key verification
    To prevent an attacker from modifying our published Bitcoin public key,
    its permanently embedded into Bitcoin blockchain in a way that is
    [nearly impossible](https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_computing_power)
    to modify (and becomes exponentially more difficult as time goes by).

    The public key can be verified by taking the following procedure:

    1. Take the SHA256 of the domain name ("****.com")
    2. Create a Bitcoin address using that hash as the private key
    3. Find the first transaction with that address as its *output address*
    4. The *input address* of that transaction is our public key

    If its ever required to change the public key, the announcement
    will be signed with the old public key.

Software packages could use the package name instead of a domain name, or the authors can attach the public key to their usernames and use it to sign all their software.