Lots of good answers here. I'll add something: give your villain a hobby. Have him be interested in something besides ruining the PC's lives.
Perhaps he collects artwork. Grand Admiral Thrawn from Star Wars was a fantastic villain and he studied cultures' artwork to understand them better--in order to crush them under the Empire's boot, of course.
If the BBEG loves opera and the PC's know that, they might stake out the local opera house on opening night. Let them meet and interact with the BBEG where combat isn't possible (because the BBEG hasn't done anything wrong, according to the authorities).
This sort of thing not only makes the villain a more well-rounded character, it makes them more interesting.