I'm a big believer in instead of villains, two protagonists with conflicting goals. Thus I find a complex personality extremely important, as well as changing over the course of the story--personality wise, I don't give a crap about power level.:P
The old example I used to use, is siblings racing to a tree to grab the apple. The two might race to the tree, but the brother/sister will still catch them if they fall. But they'll just as easily eat the apple that falls from the tree that slipped from their siblings hands.
In other words I think some work suffers from the bad guy being to evil.