As far as a villain, how about a spy/sleeper agent? I would make it someone the PCs rely on quite frequently, like a shopkeeper that they go to for all their supplies. The shock of his "turning" will enhance the campaign. I had a DM back in the day who really amplified the role of Gremag and Rannos Davl, the shopkeepers in Hommlet, as agents of the Temple (unbeknownst to us). They were our "go to" guys for buying and selling equipment. The anger and hurt we all felt when they turned on us was not only personal to our characters, but to us as players as well. A bonus for this construct is that your bad guys can learn about the PCs abilities before they fight them. This is especially beneficial when you need a legitimate reason for a bad guy having the perfect defense against a character who has some phenomenal ability that has spoiled more than a few of your best laid encounters.
Or you could go with the narrow-minded captain of the guard. She constantly offers the opposite opinion of how to handle a situation. The players say one thing--she says the other. She is basically good at heart and has the best interest of her town in mind, but she is skeptical and cautious. Traits that have served her well in times of peace, but these same traits need to adjusted now that the times have changed. In this capacity, the villain/rival is more of a foil to the characters. It would also add a roleplaying aspect to the campaign--perhaps the players need to change her attitude in order to succeed.
Or you could have both.