Reminder: leader monsters are +40 hp, +2 to d20-scaled things, and it deals 20 more damage per round (via an additional attack, or a few more points on each attack if it’s already got multiattack). Easy-peasy; makes the numbers all bigger. Doesn’t do a lot for outside-the-numbers
There’s other dimensions in which to improve monsters, of course. I recently ran an adventure with a wizard’s college which had been infested by a spirit of chaos, a death slaad with a few additional spells and lots of planning. That one relied on granting the monster a panoply of ritual-like spells to be used solely off-screen: it already had the ability to assume humanoid form, but it also had animate dead, magic mouth, Nystul’s magic aura and planar binding. Not really combat spells; specially chosen to do maximum damage in my particular. These don’t affect the CR. If anything, these are just adventure seeds; knowing that there’s a monster dropping major images here and there would work with any monster type, using a wand if it’s not in the stat block.
So that’s one dimension: plot power. Raising an army or dissolving a mob, showing an outsized set of mental stats and knowing secrets. When NPCs influence NPCs and reveal plot secrets, the details aren’t that important; if the DM says the Blod-Prinzl is the Chosen One of the Giants, it doesn’t take a stat block saying “charms giants by the thousand”. But it might say that in the adventure notes, of course!
Similarly, “increases yearly food production four-fold within 5 miles”. Of course a powerful druid moving in would have such an effect, but we hide that they would do this in the description of the plant growth spell and assume they cast it in their down time. But what about “prevents facial boils” or “eases childbirth”? Or “increases the fluctuations of lit fires” or “calls storms”.
These can engage in rules systems, of course: Food is a thing that matters, childbirth can kill, fires get lit around characters, and storms affect all sorts of parts of adventuring. Those turn into adventure elements which do need statistics; during a storm, there’s heavily obscured spaces from the rain and suppressed fires. The called up army will of course be guards, and they will be charmed, and those are both things game rules can affect.
But all together, you don’t modify the leader to make that happen per-se, you just write it into the adventure. There is an illusion here, there is a passwall there. The source of these things should be suitably impressive, but you don’t necessarily need a new block for that.
High level adventurers don’t necessarily kill monsters by numbering them to death. More precisely, by the time they’re numbering the monster to death, they’ve already trapped the monster (so that it’s subject to their mighty math) and may have ensured they themselves are untouched by the monster’s strength. For instance, flying wizards raining down fireballs against a stone giant: it’s expensive, but what’s the giant gonna do? Run away under cover ideally, of course. Encounter over. But maybe the payload’s an enlarged hasted action-surged multiattacking fighter with a flaming sword; maybe it’s an ethereal assassin. Whatever. The point is, math is half the problem, but it quickly approaches problems of engagement; speed, range, weapon immunity, and just straight up action economy.
The weapon immunity really hurts high level monsters. In previous editions, there was a ladder of magical weapons; +1 can harm elementals, but it takes +5 to hit a balor. That’s gone now, so that there’s no longer a system in the game which privileges items with plusses. There’s a trivial fix for that: a monster with protection from weapons can only be harmed with a magical weapon whose rarity equals proficiency. This will of course affect martial characters to a certain degree, but the really big effect is to make big scary monsters more expensive to attack for groups arming soldiers; even magic arrows would get pretty costly. Worldbuilding.
But even with that, there are some monsters without ranged attacks and no flight. Those monsters are dead meat. There are monsters with no ability to shut down spells, low wisdom scores, and the humanoid type. They’re dropping to a charm-type spell at its earliest opportunity, and probably joining the party to boot. Maybe the monster can’t see invisible, has no area attacks, and can be stabbed; not a problem for low-ish challenges, but it couldn’t be a Big Bad at challenge 20; it’s gonna die.
Those problems also need to be attacked. The problem isn’t math; it’s action economy, it’s mobility, it’s range. The simple solution is to make the creature legendary (move, perceive, attack as actions), give it the legendary defenses, ensure it can climb, jump, or fly. It’s still getting forcecaged, though; it’s still getting planeshifted away from, it’s still getting wall of stoned. Those are a little harder to lock down; most monsters are vulnerable to them. I think your best solution in general to that kind of lockdown is an ally with dispel magic, or some element of setting design which lets martials invoke dispel magic.