Innocent Flower said:
-Rather than tavern hunting, companions should come up, dynamically, in interesting ways that are relevant to what kind of person they are. We escort a caravan, and one of the caravaneers could join us. We save a village or a prisoner, and we might get a volunteer who does X, is of Y nation, and wants to join us for vengeance/honour and glory/because they lost everything. Maybe a soldier we train up might go POP and become a companion.
This would be neat. I don't know if you've played FTL, but sometimes you would have an interaction like this where you fight a slaver ship, or go to a space station and after fighting off the enemies and when the fight was over, you'd sometimes have someone join you. It's great for role play, especially if you have had them for a while, because you want to make sure they survive.
-Companions should be able to die (or have their own "win" conditions which have them retire and give the player and other companions a lot of xp).
Maybe you could have a quest where a companion is very far from where they're originally from ( had to leave a long time ago, escaping from a rival clan / lord), and you bring them back to their homeland now that it is safe for them to return.