Since the game is unplayable without getting at least one captain why don't ever show up in the taverns?

At the start of the game the AI has a lot of cogs without captains, that it wants to make into convois. So you're competing for the new captains. But they never put them on crayers or snaikkas, so you have an advantage here, keep checking the river towns, the AI won't snatch those.

After that first rush almost every captain that spawns is yours anyway, the white traders rarely expand so captains have a higher chance to run their timer down than being hired by the AI. So even if you don't find enough now, it will get better. If you keep checking every tavern every day you'll eventually have more than you can use.

If you don't mind future knowledge / save scumming: once you know where the first captains are in a campaign game, you can rush to get those, later ones are random but the first lot is fixed.

This is about P3, probably the same for P2, if you're playing The Patrician everything above is most likely completely wrong.