Start Off Slow
Start the villain off with low stakes, and raise them slowly. If the villain is some sort of hideous anathema creature in your game -- a lich, a red dragon, a demon, etc. -- you can introduce them in disguise or through cutouts (see below). Otherwise, introduce the villain in a conflict with the PCs where the stakes are low. For instance, start them off in a casual conversation, trading insults.
Make each escalating confrontation a competition with a win condition that doesn't include death. In our insult-trading example, you can offer the players a chance to win by landing the best insult. Trade verbal jabs, but let them get the last word. Write down some of the best zingers the villain got off.
Here's a simple list of conflicts with escalating stakes you can use as inspiration. It's not comprehensive.
Threats to status
- Simple disagreement or argument
- Competing for a scarce resource (a court case, a petition, buying the last 500gp diamond in town, trying to get to the treasure before the PCs, being more popular at the bar, etc.)
- Insults and humiliation
- Subtle, nonspecific threats ("You haven't seen the last of me" or "You have no idea who you're dealing with") - used well, when the stakes are still low, these can be ominous.
- Investigating them (asking around about them, running a background check, talking to their associates)
- Spying on them indirectly (shadowing, hacking, eavesdropping, reading their mail, stealing their garbage, magic)
- Publicly shaming or slandering them
- Turning one of their allies to the villain's side
- Unjustly claiming something that they deserved
- Stealing from them when they are not present
- Stealing something from their person subtly (through stealth or magic)
- Turning one of their loved ones to the villain's side
- Destroying their property while they are not present
- Blackmailing them
- Framing them for a crime
- Convincing an unaffiliated third party to attack them
- Hiring goons to attack them
- Robbing them with threats of violence, through cutouts
- Attempting to capture them through cutouts
- Attempting to harm them through cutouts or traps (bomb, poison)
- Attempting to capture them directly
- Attempting to kill them through cutouts (an attack that is likely to succeed, only averted by good precautions, luck, or third party intervention)
- Attempting to harm or kill them directly
Introduce your recurring villains as tangents to an unrelated (or seemingly unrelated) plot with higher stakes.
For instance, a mad wizard summons a fire elemental in town, and the PCs have to help put out the fires before the village is destroyed. A mysterious woman (your villain) arrives and starts to help, but she's constantly claiming more credit she deserves. After the fire, she disappears, and the villagers are praising the mystery woman who saved their town, to the PCs' chagrin.
Other ways to insert villains in other conflicts include court cases, tavern brawls, high society parties, sporting events, religious rituals, holiday parades, and other large public events.
As you raise the stakes, use other NPCs to do it. That doesn't expose the villain to the PCs, for them to mess with. There are really two ways to do this: The first way is to have friendly NPCs tell the PCs about the villain. The second way is for the PCs to interrogate the villain's henchmen. No matter what the henchmen say, rumors about a mysterious villain turn the mood toward fear - even if the henchmen say nothing at all:
"One takes cyanide, another would let her arm be broken, neither will talk. Who puts that sort of fear into people?"
- James Bond (Sean Connery), Dr. No
The Villain Shuffle
What if the PCs, in that sociopathic way they sometimes behave, kill your villain too early? Even if you've started with low stakes, PCs can be unpredictable. They might kill a person just for spreading false rumors about them. They're PCs. They do stuff like that sometimes.
Well first, let it happen.
Don't railroad them. Give them a chance, even if it's nearly impossible. Play by the rules and keep things fair. Then, when they succeed at killing your villain, you have two options:
First, you can play the "no one could survive that" / "never found the body" trope card. In this trope, you have the villain die in a way that the body cannot be recovered. When the street samauri shoots him with a grenade launcher, the building collapses. When the fighter cuts him down with a greatsword, he falls senseless off the bridge into the raging rapids below. It's a fun trope card to play once. If you overuse this trope, you will come off heavy-handed. Even using it once robs the players of their agency.
In a game with resurrection magic like D&D, you could always bring them back if they have clerical followers. But you will only ever get to do this once. After they've been robbed of their agency once, the players will make sure to burn the remains of every named villain they meet and Teleport their ashes to the bottom of a volcano.
You can use those tricks sparingly, but they're not the best way to handle early villain death. What's my criterion for "best," you ask?
The best way to handle an early villain death is the method that's the most fun. In this case, the most fun choice is the choice that robs the players of their victory the least.
See, if the PCs kill the villain a little early, you can just call that the end of the campaign, and it will feel satisfying. If the PCs kill the villain way too early, you can't just end there -- the players won't be happy. They expect you to make their victory meaningful. If they just killed a villain who was spreading nasty rumors about him, and you end the campaign there, it was a campaign about powerful fantasy heroes who murdered some guy who was talking smack about them. That's not satisfying for most RPG players. So you have to do something.
If you totally deny their victory by force (railroading), you've made them feel like the villain only dies when you say they can die. That's not good.
At least with resurrection magic or "never found the body," they've achieved something. They've cost the villain something. It's still a negation of their action, but not a total negation. In Pathfinder, coming back from the dead costs 7,000gp, a lot of pain and suffering, and the villain now owes a level 9 cleric a very big favor. But it's still not victory for the PCs. A "no one could survive that" situation probably leaves your villain maimed and out of the action for a little while.
The villain shuffle is where you reveal that the villain the PCs just killed was not the mastermind of the conspiracy, but instead the mastermind's most valued henchman. The real villain is the man behind the man.
You don't have to reveal this at first. When a villain dies early, often the players don't even know this was (originally) your main villain. Your new mastermind now has an information advantage: Yes, she just lost her best henchman, but she knows the PCs (who killed her are her enemy, and the PCs don't know about her yet.
Alternately, you can flip the mood quickly. Defeating a villain feels powerful. Learning that the villain's boss is going to come seeking revenge feels scary. The villain could make a good session-ending cliffhanger when he mutters, "the Queen of Shadow... will... avenge me..." before expiring.
When you play the villain shuffle, you can adjust the scope of your adventure. The original villain threatened to take over an organization. The new villain might threaten to destroy the organization. Or take over the city, destroy the city, take over the region, destroy the region, take over the country, destroy the country... etc. If you adjust the scope of your adventure, a lot changes, so don't do this lightly! Players will feel the whiplash when a "save the city from organized crime" quest escalates jarringly into a "save the multiverse from dark beings from beyond space" quest.
Last, but not least, don't forget to connect your new villain to the PCs' plot hooks. if the first villain was tied to PC A's story, then the new villain can be tied to PC B's hopes and fears, or to more than one PC's hooks.
Use Recurring Villains!
You can use a recurring villain by starting off with low stakes, introducing them when they're not the current antagonist, and using cutouts. If they're killed despite your careful stewardship, you can always play the villain shuffle.
And you should! A recurring antagonist has more emotional weight, keeps your cast of NPCs smaller, inspires more memorable stories, and feels really good to defeat.