A good villain, as it was pointed out, must be an obvious challenge for the hero - and often, the hero seen in a mirror darkly, as it were.
The Batman Rogues Gallery is an excellent example of this; most of the greatest Batman villains are dark reflections of the Caped Crusader.
Joker represents Batman's madness; the part of his mind that broke when his parents were killed.
The Penguin is a businessman - a criminal counterpart to Bruce Wayne more than Batman, but with all the gadgets.
The Riddler is the flip side of the World's Greatest Detective - a purely intellectual opposite, trying to come up with a great scheme that the "Worlds Greatest Detective" cannot solve.
Harvey Dent, or Two-Face reflects Bruce Wayne/Batman's split life - a respectable citizen on one side, and a scofflaw on the other. Note that Bruce Wayne is the carefree/careless playboy to Two-Face's monster, while Batman is the ruthless crimefighter to mirror Harvey Dent, the Prosecuting Attorney.
Catwoman is, well, she complements Batman's thrillseeker more than anything else.
I could go on, but these are some of the most obvious "other side of the coin" villains for ol' Bats, used as examples for the point.
A good villain NEEDS a bit of backstory; not necessarily a parallel to the hero's story, but usually with some interaction or reference before the hero's rise to greatness. A villain who's merely "being evil for evil's sake" without any interesting facets is just, well, a jerk who needs to be dealt with. A powerful jerk, perhaps, but if there's little emotional investment in the villain, the final boss battle becomes less... cathartic.
The Ruthless Knight who killed your parents because he thought they were blocking his path, and who's clearly a sociopath in terms of how he considers the peasantry of the land is a lot more satisfying to kill than a big, dumb ogre who ate your parents just because he was hungry and they were the closest thing to a meal at the time.