Some facts about character recruitment:
Every optional character subject to the recruitment mechanic has, at minimum, a Support level that they must reach with the path's main character, and a Renown level that the character must reach. These numbers are different for each of the four flame lords. Before you can even attempt to recruit them, you have to give them at least one gift, which makes it possible to start building Support with them through meals.
Renown correlates mainly to your progress through the main quest, as winning in the games is the biggest source of it; neglecting subquests or your lord's unique mechanics might leave you a bit behind the curve. No character requires more than 10 Renown to recruit, while the cap is 12, so you'll eventually be able to get anyone. The Renown requirement for recruitment is basically an indication of how early you can get them.
The Support requirement is more constraining. The characters requiring only support level 1 are free and tend to be very useful for the upcoming main story quest. Characters requiring support level 2 are pretty easy to pick up and will keep your army well-rounded. Characters requiring support level 3 need a long time to work on them and carry a high opportunity cost, since meals and gifts both count as weekly events that refresh on Sunday. So you'd better choose one that you really like. Getting someone with high support but low renown can be a real project, and catching 'em all might require taking advantage of the fact that support points can never be revoked, even if you change paths or return to an earlier chapter.
Most recruitable characters also have a "Negotiation" requirement. This means will also request an item delivery, and while you can't see what the items are until you meet the Support and Renown requirements, it will give you an indication of whether it's common/cheap or rare/expensive. Sometimes it'll be something you can only acquire in the overworld in hard-to-reach areas, sometimes it'll be something you can just buy anywhere.
Additionally, some of them will require you to clear a quest before you can recruit them. That might be a simple, lenient subquest that they give you as soon as you attempt to recruit them, or it might be a paralogue.
Paralogues can be missed! This mechanic kicks in starting in calendar month 9. The availability to accept or complete paralogues is sometimes constrained by very tight deadlines, and unlike main quests, you can't automatically travel to their destination, so they can be both overlooked and permanently missed. Top men are working on compiling a spoiler-free list of the relevant date ranges in each path. It is possible for a character with a low Renown requirement to still require a paralogue that can't be started until much later.
(Speaking of things that can be overlooked and permanently missed, there are random scenes like base conversations that can be viewed on certain dates in Dagsion. These appear on the map with a faint animation while they're available, but the Dagsion map can't be viewed while you're not in Dagsion, so hopefully there'll be a list of those someday too. But I'm not gonna sweat it.)
Not every character can be recruited in every route. However, among the characters who never join automatically in any route, there is only one who's exclusive to a single route: Gaitz can only be recruited by Dietrich. And that's a difficult one to get, requiring 3 support, 10 renown, and a paralogue that's only accessible for a single day.
In general, if you're going to recruit someone, it's best to get them in as early a chapter as you can. This is because of the way that automatic level scaling works. Characters who are recruited later tend to have lower stats on average than they would if they had been gaining EXP normally. This is so weird that I think it might be a bug, and therefore liable to be patched out in the future. They suspect maybe that they're only applying their personal growth rates to automatic leveling, and excluding the increasingly significant class modifiers to growth rates. This is bad news for characters with high Renown requirements.