A good villain can make a game! Whether it’s a mustache twirling, cape flapping stage villain, or a dry as dust lich whose plans extend over decades and centuries, you want a BBEG (Big Bad Evil Guy/Gal/Group) that the PCs will come to hate.
Presuming you’re going campaign mode, and not just a whole bunch of picaresque adventures, you want to introduce the villain early, even (or especially) if only by rumor. Any good villain will make extensive use of lieutenants and minions to achieve their goals. Really effective villains will manage it so that the lieutenants and minions won’t even realize who they're working for. The best villains will make use of those who think they’re actively working against them. Bonus points if you can get the PCs to do the villain's dirty work for him!
The best examples of how I try to run my D&D villains don’t generally come from books or movies. That isn’t to say I won’t steal a good villain from a book or movie, but if I want a long term BBEG I look to TV. More specifically, to Buffy The Vampire Slayer.
Buffy did an excellent job of showing how to run villains over it’s first 4 or 5 seasons. Starting with season 1 they jumped right in with The Master, an ancient evil vampire who mostly controlled the vampiric happenings around the Hellmouth, but was himself trapped. It wasn’t until various minions and lieutenants had been defeated, and more information gained that Buffy was able to finally confront The Master.
While the Master was a pretty solid and classic villain, he was a little one dimensional. Evil, evil, kill the slayer, open the Hellmouth, end of the world, feed on humanity forever, etc. There isn’t any subtlety or surprise. I’ve always appreciated a little more nuance from my villains.
Season 3’s primary villain was The Mayor, and as a character he was much more interesting. He was talked about in season 2, but not shown until season 3 (rumors!) and when you finally do see him he’s… He’s happy. And nice. And polite. A little bit of a germophobe. He reminds you more of a 50’s sitcom dad than an evil mastermind. I found myself liking him, even rooting for him a little bit.
The Mayor made himself generally inaccessible to Buffy by being the mayor. It also helped that he was invincible, at least until he turned all demon snake. At the same time he didn't just go and try to kill Buffy and the gang. He's got bigger plans, and they can be useful. He even turns Faith to his team!
My advice: if you want to run a memorable villain, find some that were memorable to you, and figure out what make them work, then steal that and go!