But what about to their followers? The conqueror is obviously legitimate to their followers, its why they are following them in the first place, so why shouldn't the conqueror get a legitimacy boost for conquering territory?
Plenty of conquered people's have accepted their conquerors as legitimate, even if only in a pragmatic sense. Most places that are conquered don't immediately go into revolt, that usually takes a couple of generations so conquerors getting buffs to improve stability post conquest is also perfectly fine. For example, there were no major Christian uprisings in the Sultanate of Rum or Muslim uprisings in the Crusader States. External pressures or internal dynastic struggles are what usually weaken and eventually lead to the collapse of Medieval states. Internal revolts are a symptom on central weakness, not a cause.