I think a compromise would be to add to the random generation of Willowbarks and Sheildmaidens a generic - low level - companion to level as you saw fit. I'm Gilford the Farmer, and I'm bored. I'm Axios the Runaway, keep me from the chain gang and I'll murder for you. I'm Bella the Headstrong, what I lack in experience, I make up for in will.
Gives the player a bit of agency - I need a healer, I need a steward, I need something the devs havent thought of - and you have less of a problem early on (remember, getting a companion is part of the opening quest) running into "...I'll just need 127 lb of gold you might have laying around and I'll join up with you." every time you talk to anyone in the tavern.
Half of my campaigns I can't find the companions I need, I have to wait for them to hopefully spawn in.








