One thing to watch for with your villains is survivability. I don’t just mean in the combat you’ve designed for them.
If It Has a Stat Block, It Can Die
This is a basic rule of writing tabletop RPGs. The moment you stat up a character, you’ve given the GM instructions for how fragile or vulnerable that character is. Even if it’s a deity at CR 40… you’ve now created conditions for that creature to die at the hands of the PCs. So be very careful when introducing stats for your villain in a published adventure. If this is a multi-part adventure (such as an Adventure Path volume) you don’t always need to stat out the characters right away. If the PCs see this person in book 1 but don’t fight them until book 3 (at least that’s what you’re planning), then don’t publish stats for them until book 3.
If a GM has a villain listed with no stats, they can more comfortably hand-wave any attempt to assassinate them. You want to ensure they vanquish the foe when you expect them to, not earlier. Otherwise it can throw off the tempo and plot of your story.
The Upper Hand
If your villain appears in front of your PCs before you’re ready for them to do battle, make sure they have an “out” from an enterprising PC who wins initiative, critically hits, and murders your villain before they can finish their BBEG speech. Common, but trope filled, are: illusionary BBEG, clone of the BBEG, simulacrum of the BBEG, contingent teleport spell. You can do some other things that limit the PCs abilities against the BBEG such as having them on higher elevation before the PCs get access to fly spells. They may also have some extra protection against ranged attacks such as entropic shield, protection from arrows, fickle winds, or wind wall. Putting a portcullis between the BBEG and PCs allows them the ability to taunt them from behind cover without opening them up to melee attacks.
Make Their Presence Known
Build up a BBEG’s infamy in the eyes of a PC before they meet them. This can make them feel very present in the campaign, even if the PCs are unlikely to see them in person until their final confrontation. Have the PCs find written instructions on a henchman, signed by the BBEG. You can start with just initials, enough to keep them asking who this person is. Later give them an entire name. They’ll start to get to know the villain through their notes and instructions, the way they treat their henchmen, and the stated goals in the notes.
Create some gossip around the latest settlement that helps inform the PCs about the villain. Feel free to include exaggerated or false information, as this will keep the PCs asking questions about the villain and help build more mystique. By building up the reputation of the villain in the world, it helps to make them seem like a much bigger threat that the PCs need to deal with.
This is VERY difficult to pull off, only because a lucky hit or massively damaging attack can bring a character down from high hit points to unconsciousness in one hit. You can’t guarantee that they can escape to harass the PCs again. The only real way to do this is to have clones/simulacrum attack the PCs before they hunt the villain down for a final showdown. A contingency spell can get a BBEG out of harm’s way and to a local healer; this works great when paired with an amulet of natural recovery or lesser talisman of life’s breath.
Make sure you have a plan for how to move the plot forward if the PCs do manage to slay them ahead of schedule. Including information like this in a side-bar is really valuable for GMs who have players that like to “break” adventures. The BBEG appears to taunt them and a lucky gunslinger critical for 4x damage finishes the boss off in one hit? What do you do then? Have another way to move the story forward.
Remember, if the PCs can see it and it has stats, they can kill it.