Maybe we could assign roles to them by giving them certain weapons and telling them to take that skill instead of another.
I remember playing Final Fantasy XI and they came out with an adventuring companion you could give weapons to every couple of levels. You could open a menu by talking to them and ask them various things like what level it was or how they acted in combat, whether it be aggressive or ready to support or heal. Then you could be asked to give it a specific kind of weapon like a low level katana, then when it levels up, a mid level katana and so on. Maybe for Ultima Online you give your hireling a spellbook of whatever type and some gear.. Give it like 3 skills it can take and it just rolls with you where ever. Maybe lessen its damage or something to compensate for the OPness.
Edit:
And pre-requisites, can't be on a trial account, must own a house, maybe complete a quest for them to 'bond' with you, vary the quests, maybe give them some cool dialogue options like those heralds had. Let them express interest in getting paid for their services or remind you they need to eat too. If you want to stable them you take them to the inn, or put an innkeeper in your home. Maybe spjce the rp aspect of it up by making us sign a registrar or something. If you want to rename them or reset their templates you can swing by the respecting trainers and exchange gold and answer questions for them.. There could be a lot of interesting options here. Still I think boosting mages and adding cinnamon rolls in game should be implemented first.