*waves to SemperJase*
The first thing to think about when creating a villain is that they are, first and foremost, a character. So the rules for creating a great character obviously apply to creating a great villain -- they have to have REASONS for doing what they do, they have to demonstrate a consistent identity, they ought to have relationships (even if they're sick and twisted ones) with other characters and so on.
What's special about villains is that their goals conflict with the party's goals. This doesn't have to make them evil, though in a campaign like SHARK's it probably indicates it pretty strongly. But the truth is, as long as the villain's goals and the party's goals are in clear conflict, the villain will largely propel themselves into action against the party. The thing to do is to make sure that the goal is REALLY IMPORTANT to the villain, that they will stop at NOTHING to achieve it. If the party are equally committed to THEIR goal, your work is done -- just sit back and watch the fur fly!
One of the most memorable villains in my fantasy campaign was an accountant. A perfectly ordinary, sort of cute and perky accountant. She happened to work for a family that was in direct rivalry to the family the party were working for, and she was given the assignment of finding out who these clowns were and what they were up to. She proceeded to make total fools of them, get one suckered into a duel (during which he broke the law, got himself arrested, so she was kind enough to get him released -- after getting him to blurt out the big secret about why they were in town) and get the whole group declared persona non grata in that particular town. They truly HATE this woman. And fear her. Whenever they hear Collette's around, total panic sets in and usually they head for the hills. They know they're about to get snookered into a plot beyond their ability to unravel.
All for a 1st-level Commoner with smarts and a high Charisma. She's not even evil -- just opposed to their goals. Heh, heh, heh.
You don't evil. You don't need super-powers. You just need real personality, ruthlessness and brains. That will scare any party and create a truly memorable villain.