Ruthlessness. I like a villain that has no qualms with disemboweling a foe or an ally in order to make his power as absolute and unquestionable as possible.
A good example is Emperor Golgoth from the comic series Empire. In one issue, Golgoth was in the midst of a negotiations meeting with the ambassador of Greenland concerning the elimination of a secret military installation that even the ambassador was unaware of. When ordered to dismantle the base, the ambassador refused and basically said "there has to be a reasonable explanation for this." Golgoth's reaction was to target the man's home with a satellite laser system and murder his entire family while he watched. A tad brutal, no? That's what I'm talking about.