Someone recently asked; what makes a great villain? While the context around the question was in a roleplaying game mileu, I think it makes some sense to talk first about what makes several fictional villains great from movies and books, and examine a few of the most iconic ones and what their appeal is. Partly because that's my own personal favorite mileu, and partly because it's one that's ideally suited to roleplaying games, I'm going to focus on villains that would fit in a pulp, serial, or comic book mileu in particular. Then, after I talk a bit about why some of these really memorable villains were memorable, let's talk about how to adapt those ideas into a gaming context.
Here's a few examples of what I consider really iconic villains; the kind that I'd love to emulate in my campaigns.
1. Often credited as the first "supervillain", Professor Moriarty is a great place to start. The first thing that made Moriarty compelling is that the superhuman Sherlock Holmes himself has met is match in the man. He's a prodigious intellect, and is a criminal mastermind, with his manipulative paws on all kinds of things that Holmes has to thwart. But that doesn't mean that he's a patsy to Holmes; what Holmes thwarts are some of his minor minions, not the greater schemes. Only in "The Final Problem" in which Sir Arthur Conan Doyle meant to kill Holmes off and finish writing about him, does Moriarty himself put in a personal appearance. Despite that, Moriarty recurs at least as a shadowy name in the background. Keep this in mind. It's going to be my advice, actually, to not have your villains make a last minute first appearance just in time to be defeated. But certainly there needs to be their mark, their sign, evidence of their handiwork in all kinds of problems that the PCs thwart.
2. Comic books are in many ways the successors to the pulp aesthetic, and they've given us some of the most iconic villains of all time. Doctor Doom is a good one to start with. Doctor Doom's appeal is in large part due to his charisma. He's got a very iconic and unusual visual image; instantly recognizable, sinister, and melodramatically villainous. Perhaps most importantly, Doctor Doom gets seen. A lot. A big part of the reason folks love to hate Dr. Doom is because they feel like they know him. He's not a mysterious shadowy figure who only gets seen occasionally; he's always showing up.
3. Along those same lines, I give you Magneto of X-men fame. Magneto's got everything Doctor Doom's got and more... he's also sympathetic. Especially since the early 90s, Magneto has been presented as a very reasonable, charismatic and personable villain, and sometimes you don't wonder if maybe he's on the right track and Professor Xavier is just a hopelessly naive hippy with his dreams of humans and mutants living together harmoniously.
4. Also building off of Doctor Doom but going a different direction, I give you Darth Vader. Just to be clear, I mean Darth Vader before the badly concieved prequel trilogy. Darth Vader only had about six minutes of screentime in the original Star Wars movie, but he made every second count. He was one of the first characters to be introduced, and he appeared throughout the movie. His notable traits include a very sinister, iconic and unique get-up, very casual evil (further built upon when he kills officer after officer in Empire Strikes Back for minor tactical failures). And as the series progressed, we can see the evolution of an iconic villain for the ages. We saw more of him. He became sympathetic. His fall from grace into villainy was shown as a mistake that in many ways he regretted, even though he could hardly undo it. Of course, Darth Vader is rehabilitated and repents (fatally) at the end, but that's not what made him so iconic. He was already iconic before he did that. Part of what makes him so appealing as a villain is that he represents temptation. When he springs the horrible surprise on Luke that he is his father, he makes him the offer to join him, overthrow the emperor themselves, "end this ruinous conflict" and rule the galaxy side by side as father and son.
So what can we learn from looking at a snapshot of a few iconic villains? First of all, the best ones are not one-dimensional. Even Professor Moriarty and Doctor Doom are given tragic, sympathetic traits along with their evil. Secondly, very few memorable villains only appear in the background. By that same token, Sauron himself isn't memorable; it's his war machine and his Ring specifically that represent Sauron's evil. Rather; get your villains up on center stage. Make sure the PCs have to interact with them in ways other than simply a big fight in which only they (or the PCs themselves) are left standing. Take a page from the X-men/Magneto relationship---sometimes, as much as it pains them both, they even have to join forces temporarily or find themselves on the same side of some other conflict.
Like Moriarty, make sure that they're at the center of lots of shadowy things going on. Sometimes random evilness is good, but more often than not, you should be able to tie a string back from that random evil to the villain at the center of the web like a fat spider, pulling strings.
Maybe we can get barsoomcore to chime in on his success with his Barsoom campaign's villains; all folks I think are very memorable.