Though I wouldn't say that the character and history of Majora is quite as well developed as the Skull Kid's, I found Majora to be an excellent villain, and one that clearly stands apart from the others of the series. Here's why:
While the Skull Kid's history tells the tale of him losing his friends, the Four Giants (and how lonely he became because as a result of this), at this point in time the Skull Kid was by no means known to be a highly destructive individual. Mischievous, yes, a prankster, yes... But a villain bent on destroying Termina? No. Not by a long-shot.
The Skull Kid, while misguided and confused by the departure of the Four Giants, was not capable of perpetrating the evil that Majora displays. Sure, he was said to have gotten a little more angry and vengeful after the Giants left for the four temples, but it was Majora that influenced the Skull Kid to enact the most devious punishments upon the people of Termina, not the Skull Kid himself.
However, this matter is obviously up to some debate. To me, it appears that the nature of Majora's influence upon the Skull Kid could have been one of the following:
1) Majora influenced the Skull Kid, augmenting the Skull Kid's loneliness and desire for revenge, but didn't exactly take him over. This left the Skull Kid to wreak havoc with new-found powers, which ended up enacting the destruction Majora also desired.
2) Majora may have simply assumed the identity of the Skull Kid, a known prankster in the land of Termina – a perfect cover for a rampaging psychopath bent on destroying the world (Majora is still a mask after all, and might have been worried about being sealed away again). After all, Majora does call the Skull Kid a “puppet”.
3) Majora and the Skull Kid may have fused personalities (like the Symbiote suit when it bonded with venom in the Spider-Man series). The two may have had opposing goals at the beginning, but the strength of Skull Kid's sorrow may have caused Majora to unhinge a bit, and begin questioning its own identity, and state of being.
Once it casts the Skull Kid aside, Majora proves itself to be a strange and confused being on its own. I've heard theories that state that Majora is the spirit of an entity that was trapped within the mask. Though the mask may simply be a vessel into which a torrent of dark energy was poured, the fact remains that Majora's Mask has a mind and spirit of its own, separate (yet similar) from the Skull Kid's.
Majora itself can be seen as a sad, child-like being when encountered on the moon – a being that seems to have trouble understanding the difference between right and wrong. The other moon children pose moral questions that lead one to believe that Majora is an entity that is unable to answer these questions, leading one to the conclusion that Majora is a being of unrestrained chaos.
The fact that Majora is a mysterious, faceless horror that perpetrates acts of chaos and destruction without moral guidance makes it one of the most interesting villains of the series. While a villain with clear motives makes for a more logical, arguably robust character, a villain driven to satisfy the needs of its own insanity makes for a much more unpredictable, frightening character.