Now, fundamentally, there are two types of villains in games, or perhaps it would be more accurate to say that there are two types of antagonism, which are often present in one single character. For the sake of the discussion, though, let's have these as two types. Extra Credits calls them "mechanic" and "narrative" villains, Robin Laws would probably call them something like "procedural" and "dramatic" villains, but in my head I call them "challenge" and "choice" villains.
Your challenge villain is a villain who presents a threat or obstacle to be overcome or avoided. A typical challenge villain would be someone like a James Bond villain or Lex Luthor, or maybe a big tough monster to fight, like a dragon in D&D. A challenge villain is pretty recognisably an opponent you have to fight, and the fun comes from the tension and uncertainty of whether you'll succeed or not and from the interesting puzzles of trying to do so.
So what makes a good challenge villain? Consider a typical comic-book supervillain, someone like, I dunno, the Prankster or somebody. I assume that most people with the literacy skills to read comic books don't think that this is going to be the issue where Superman finally gets killed by some douchebag with a moustache. Check out this cover: it actually makes a point of the fact that Superman is impervious to whatever the Prankster wants to do.
It also helps if the villain himself is entertaining, which may actually be an area where the Prankster falls down, but if you're having a lot of fun watching Frank Gorshin be the Riddler or Doctor Doom call people dolts, you're gonna enjoy it more than if you have to watch some stubbly oaf grunt his way through the plot. Careful, though; a little grandstanding from a hammy villain goes a long way.
This means that effectively-designed challenge villains have to be fun and interesting to fight. A villain who is just a big block of hit points and damage sitting in an infinite plain of blue squares is no fun to fight -- you just slug 'em and you either win or you don't. But a villain in an interesting environment full of tactical hazards and opportunities, or a villain with just one weakness that you have to figure out, or a villain who is much more powerful than you but not too bright so that you have to outwit her with trickery and misdirection? Those villains are fun.
In an open live game, it's especially cool if you can use the world around you to figure out how to fight the opponent instead of just being told. For instance, if you know that this guy is a real tough customer, but then you hear from a completely different source that there's this guy with one blazing red eye who goes to Granny's Pie Shop every morning because he can't get enough of that cloudberry pie and you think "hang on, that sounds like Zergathrax...," that's a very rewarding moment.
A choice villain is an antagonist where the challenge is twofold. Not only do the PCs have to win in the first place, but they have to decide what to do about the character. A classic example would be the Green Goblin from Spider-Man. The Green Goblin is a mad villain, sure, but he's also Spidey's best friend's dad. If Spider-Man reveals Norman's identity, Harry will be devastated. If he tells Harry directly to prepare him for the impact, he'd be giving away the fact that Spider-Man and Peter Parker are the same person. But he can't let him go, because then he'd be responsible for his future crimes! And so on. (Note: this is not an accurate summary of the actual story in the comics, it's just an example).
So a choice villain is less about "how do we do this?" and more about "what do we do?" Sheriff McGee has brought peace and stability to this frontier town -- but he's wanted for murder Back East. Dark Lord Zergathrax cares nothing for the value of human life -- but if I kill him amn't I just as bad as he is? Catwoman's crime spree has cost the city millions -- but I can tell she's not really bad at heart.
You'll have noticed a few things about these examples: first, a lot of them have to do with crime and punishment. That's because cop or cop-like characters are really easy to put in these situations (this is why The Shield is a much better show than Sons of Anarchy, incidentally). The second is that none of these dilemmas are actually posed by the antagonist. Sheriff McGee, Dark Lord Zergathrax and Catwoman are all just doing the thing they do, and by interacting with the setting and characters they produce a moral question (not necessarily a dilemma, but a question).
You will sometimes find an example where the villain poses the moral dilemma directly, say by firing off two rockets, one headed for downtown Metropolis and one headed for the middle of nowhere but with Lois Lane tied to it. Or whatever. This ... this can work. If you have a villain who is trying to get people to compromise their own morals, maybe a literal demon or just a metaphorical one like the Joker in The Dark Knight, you can get away with it. But a little bit of it goes a long way. Do it more than every once in a while and you start to see the subtext becoming text, especially when it happens from villains who have no reason to care about the hero's priorities. "Compromise your morals and you can beat me -- wait, why am I telling you how to beat me?!" It works a little better if the villain wants something that just happens to violate the hero's principles: "why all this fuss, 007? All you have to do to spare yourself this pain is tell me the name of your informant."
In essence, then, the good choice villain is just a special case of the world at large -- by existing and doing what it does, it forces the characters to make difficult choices. It only needs to be an antagonist because a) it's fun to have challenge and choice in the same package, and b) it's a good way to bring those choices up for characters who are at moral rest in the status quo.
One risk of the choice villain is that the GM will decide which choice is "right." I recommend against this; the game world is supposed to ask, not answer, the questions.
Stuff I haven't talked about
I mentioned before that these types of antagonist are actually frequently the same thing -- we can't wrestle about what to do with the Green Goblin once we catch until we actually, y'know, catch him. And honestly I think that effective challenge antagonist design is probably more difficult than the other thing, if only because players in these types of games will usually provide the moral context themselves. And I didn't say that the whole thing flies completely to bits if you get someone who plays as if the setting and NPCs didn't matter. But it's a start.