The thing that makes people interesting is how well we can relate to them. It's easy to verify this - just go to any social gathering and talk to a few people - you will find that the ones you get on well with are the ones that you share experiences, ambitions and predilections with.
This extends to the relationship between readers and villains in books.
What is your target audience? If it's a bunch of geeks then make your villain narcissistic accompanied by being extraverted, more open to experience and more prone to (non-clinical) depression (source: 5 Traits Mark Out The Geek Personality).
If your audience is dictators then make your character charming, charismatic, and intelligent, brimming with self-confidence and independence, exuding sexual energy, extremely self-absorbed, a masterful liar, compassionless, sadistic, and possessing a boundless appetite for power (source: The Mind of a Dictator).
Trouble with the above is that you limit yourself by targeting a certain audience (unless you're going for a niche market) so you might want to look at the traits that the whole of humanity shares. In fact, you might want to consider trying to discover the humanity beneath the façade of your villain. Where is your character hurting? What flaws are there? What hidden hurts hide inside that stern exterior? Reveal those things to your readers and you might just make your villain interesting to them.
That reminds me - isn't there a series where the main character (a bad man) goes to see a psychiatrist regularly? Hold on, let me look it up ... Breaking Bad? No. Mad Men? No. Analyze This? Yes, but that's not the one I mean. Got it: The Sopranos! That would have been a good vehicle for your villain to get in touch with his humanity. Pity it's already been done, but I'm sure you'll think of something else.
Good luck with your writing.