For me the toss-up was between demons/devils, liches, and dragons. Here's why I ended up with liches:
demons/devils: Evil, wily, and a truly great nemesis but their primal connection to evil makes them more two-dimensional in their aims and their outsider-ness makes them less directly connected to the affairs of the world of the PCs. They are the ultimate invader.
dragons: They are the classic, archetypal monster. Not a villain, a monster. They are made to represent a mythic idea, a harrowing of hell. Destroy the dragon and the kingdom attains it's happily ever after. Dragons are aloof and above humanity. Monsters are, ultimately, a scapegoat and a proxy for issues that can not be resolved -- an enemy fabricated as an imaginary solution to a real problem.
liches: Ancient, powerful, and all too human, the lich has a full range of complexity, and solid connection to the PC's world (of which he was once a part, after all). The interesting thing about a lich is how his past relates to his present. There is a source of tension and dichotomy here. The lich also represents a theme of absolute power corrupting absolutely, which is a great theme, especially as it is tinged with fatal flaw. The lich is, ultimately, the result of failure of the ultimate test. He damns his soul eternally, unable to resist the lure of an ultimately unattainable power. He loses everything, but can never truly attain what he seeks in return. Given this ambiguous existence, what is the lich's goal? Does he seek material power to fill the void left by his unattainable spiritual goals? Does he descend into the depths of madness? Does he become spiteful for his mistake, too proud to admit defeat, and lash out with destructive rage in a seemingly random and unfocused manner? Does he go into denial, becoming a reclusive hermit, refusing to admit to his condition and trying to live on in a bizarre and delusional mockery of his former life? Woe to he who dares to confront such a lich with the truth!!! This fundamental aspect of the lich ultimately being a failure I think is central to the idea and makes for a great, colorful nemesis with a great variety of goals and characterizations.
He is a tragic figure, and a bit of sympathy makes for the best villains, as what truly frightens us are those aspects of the villain that we see echoed in our own hearts. Every time you do something that you know is not the right thing to do, when your greed or lust overpowers your sense of morality and ethics, the lich laughs mockingly at your failure, for miserly loves nothing more than company.