This is an idea I had last night as I went to bed, inspired by Tim Brannan's quick post about the level titles.
Have various social groups in the campaign world. They can be military/knightly orders (Templars, Teutonic Knights, Knights of Malta, etc.), religious orders (Benedictines, Tendai Monks, etc.), adventurers guilds, thieves guilds, magician's guilds, that sort of thing. I think some of the flavor text from early Magic: the Gathering sets might actually be good fodder for this. There were groups like the Order of the Ebon Hand, Benalish Lancers, The School of the Unseen. Lots of good flavor.
Each organization has its own titles that they award to members as they rise in power. How do the people within the game world determine that? Who cares? It's a game.
But if PCs belong to one of those organizations, they get a new title from the group every time they go up a level.
DMs would need to come up with lots of cool titles, but it could be a lot of fun.