This is only something that just dawned on me tonight, but when you finish all of the quests in Westfall, Gryan Stoutmantle bestows upon you some kind of honorary title, like “Champion of the People’s Militia” or something like that. And I know during the Onyxia quest-chain, you’re eventually granted a title of some sort, I believe from Bolvar Fordragon (like… Deputy or something? I don’t recall the specifics).
I don’t want to just go nuts with titles – I feel like the PvP titles are already pretty prevalent, I think too many options kinda rob them of meaning – but given these are a few quests that specifically note in the text you getting some kind of title, I feel like it would be a cool touch to actually get those at the end of those more elaborate quest-chains.
Just my two cents!