The most important thing about a villain are his plans and his motivations. A villain will always be just as cool and memorable as the things he does, so coming up with a creative and interesting goal needs to come before anything else. Then I think about why he does it and want it, because that already determines to a great extend how he will act and behave. Based on that, you can start thinking about an individual background and primary abilities he uses. And last comes deciding on a class, ability scores, special skills, and the like.
What he does in a fight really isn't that important, because likely the PCs will engange him in combat only once or maybe twice. What he orders his minions to do is what defined the bulk of the adventure or the campaign.