In many games you have enemies, foes, and challenges. But only in a handful does the faceless foes you are tackling rise up to become something more personal. It is when one NPC (and rarely PC) qualifies as a true rival, a counter to your every action, and eventually a battle of wits so profound they become the topic of table stories for years to come. Those foes are a true Nemesis, and it takes quite a bit of work as a Storyteller or GM to make one happen.
When building a Nemesis for your part there are three primary qualities you want to invest in them:
1. Direct contact with the characters.
The big and very important difference between a final boss of a dungeon and a returning nemesis is the personal touch. Some level of interaction must happen between the PCs and the foe. It can be in persona, via view screen, magical image. There needs to be a 'look em in the eyes' moment.
Back in the day I had a Magneto knock off in my Aberrant game. Called "Ivan" he was a crime boss who developed powerful ferrous kinetic powers with who the party fought against frequently. But he was canny enough to have escape plans and minions powerful enough to hold the PC's off. He wouldn't have been effective if the first time he showed up in my game he didn't have a face to face with the group. They had shut down a brain harvesting operation of his in San Francisco and when they were trashing the brain processing (super drug made from nova brains) plant he was there! They had a few rounds of combat when he pulled the roof of the building down on them and fled. After that the kept running into him: a voice over a loudspeaker, him waving a security footage from robberies, threats to the PC's via the internet. Eventually when the final battled happened it was personal and the group pulled out all the stops to take him down. And man what a fight. My players still talk about that take down to this day.
2. A valid reason to hate or pursue the characters.
This is the D&D lich problem. Why in the world would a high powered foe like a lich even care about level 1 adventurers? He's throw a skeleton horde at them and let them be slaughtered. Always consider the appropriate scale of the players power to their foes. Being more powerful is one thing, but the PC's must have the ability to threaten the Nemesis in some way.
Let's take a bad Exalted example: A game I was playing was a circle of Lunars trying to restore (or destroy if it couldn't be saved) a small bastion of Lunar power that an elder established years ago. We were sent into investigate a strange corruption which turned out to be Infernal Exalted and demon cultist trying to convert the country to their cause. For a while there we were looking for the Infernals behind the taint. We had long harsh battles against demons summoned in the area, had to take control of the local government to weed out cultists, and then focus on training the local mortals on how to protect and defend themselves. At one point in the adventure we finally drew out the Infernals who were behind the operation and I must say it was quite the fight (as most Exalted fights tend to be). Two Full Moons (me and a long time friend player) went to town on a Slayer and we defeated him through attrition! The Infernal Sorcerer escaped but we discovered he was working for someone else...the Yozi? It was there the 'valid reason' was both broken and supported.
This is the trap of the 'valid reason' issue with a nemesis comes up. Esclation of threat. The ST was wrapping up a game by raising the stakes in the adventure but then we as the PC's were faced with having to handle a demon so outside of the scale of how we thought that we might play. This new foe was faceless, over powering, and yet we were expected to face it. The Infernals we were facing...just a new type of lesser foe (sad as they had the potential to be more). All the other 'next tier' foes we could have faced? Just more fodder. So when moving up an organizations or tiers consider the scale of your game very carefully. This was an issue with prior editions of Exalted that 3E looks to adderss, but I've seen it happen in D&D games were the PC's take out a low level necromancer and suddenly discover he's just a pawn of Orcus...at level 5. Ya. No.
3. Build for a theme not for points.
Years ago I saw cool merits and flaws that talked about rivals and thought it would be perfect to have one in a few games. The catch is a rival is not a Nemesis, not even close. I have fits these days thinking about folks taking disadvantages that define for me who their Nemesis is. A Nemesis is not just raw points, it's something that comes out of play. Hell, a true nemesis may not even be as powerful as the party. The catch is they impact their lives and causes problems in the long run. Think of Spiderman, he has countless foes but his one true Nemesis long before the Green Goblin came along was J. Jonah Jameson. Jameson is not a bad person, he's not a nice person, and he is most definitely not someone who Spiderman will punch through a wall in a fight. He's a man with one very specific type of power, the power of the press. Jameson's position gives me the security to paint Spiderman as a threat to the city with little to no blowback on him!
In say an Exalted game, a local priest might decry the players as Anathama, calling in the ire of the Wyld Hunt, or local leaders unwilling to deal with demon allied warriors. Sure it would be easy to kill the priest, but doing so would only prove his point. Especially if the players are trying to win a Public Relations victory for their cause.
What about games like Shadowrun? Who is your Nemesis? A mega corp? They are too big and faceless. Sure maybe a Chairman or Manager is your hated foe, but killing them with out a contract will just bring corporate security and assassins down on you like thunder. But you can get back at them indirectly by taking jobs that hurt their bottom line. You can hurt their credit standing and clout in the corp
If you build a foe based on just points they become juicy targets for the players. Sure, somewhere in that threat is a NPC that you can lay hands on, but the idea of a good Nemesis reaches beyond them. It is their contacts, their alliances, their impact. Taking a good Nemesis out means taking down that support network before going in for the kill. If in an Exalted game your foe is a Deathlord you have your work cut out for you. You have Deathknights, ghosts, cutlists, and a slew of potential allies to deal with first.
And we'll call this #4.
When you take out one Nemesis you are not always done. Often there are others that will take up their cause, secret plans in the works that may bore fruit long after they are dead, or even a price to pay to remove them. This need to impact the PC's heavily. Think of Jim Moriarty from the recent Sherlock TV series. He set it up so even if he was dead Sherlock had to die to save his friends. So much so when he noticed that being alive was a liability to his plan (spoilers) on the roof scene of the 2nd season...he killed himself to carry out those plans. Now THAT is a Nemesis.
Just a few ideas to keep in mind when building one for your players.