I'd like Regnal names, at best. For a ruler to take on a different 'name' for as long as he rules, maybe with the choice to keep it after. But anything else, as far as titles go, I think the playerbase aptly decides in recording history!
I like this idea... And will make a note of it for multiple things, but I'd do a separate request on this. It'd be nice to get governments to be more than "we vote on these positions".
Vita, I don't think the nickname voting concept would be that hard to implement, for what it's worth. A couple tables at worst, I think. M&F might even have one or two separate things you could rip the logic from for it... Remind me to take a look this weekend.