How about making the default avatars a hash of the key or key fingerprint, not the username? Even the most ignorant user would then rightly suspect, when the avatar changed, that they were talking to a different person.
Separately, another programmer-artist made a program to hash forum usernames to pictures of cartoon cats, subsequently extended to hash usernames to birds (also in Rust), and to hash usernames to foxes, squid, and abstract art. These seem to have about 15 bits of entropy. Not enough to avoid malicious collisions, but enough to avoid almost all mistakes.