Status messenger has a nice naming solution. They give everyone a three-random-word name when they join (an Ethereum pub key is under that of course). Then (1) your friends can assign to you their own nickname for you, or (2) you can buy an ENS name that is globally findable.
I think of this basically like car license plates. You can optionally get a vanity plate.
Another project that I love is BrightID. It really embodies the idea that we don’t actually need a global registry of names for most use cases. Most of the time we just want to know if someone is legit or not. A web of independent Rolodexes is enough to determine that.