Anonymous Gravatar Problem
Encrypt the hash using the public key of the avatar server with ECC. This has a space overhead of 32 bytes (43 Base64 characters). A modern CPU should be able to decrypt about 10000 messages per second per core. If a website uses a fixed key for all the avatars both sides can cache the shared key, so they don't have to pay the cost of the key exchange all the time.

While this solves the "everybody can do an offline search to guess the email matching a hash" problem gravatar suffers from, it doesn't solve all its privacy problems. In particular the avatar service can track users, and the picture data itself allows correlation across sites, even if the hash differs.