Really? You thought that some musclebound bully name Bluto was Popeye's archenemy?1
Actually, Bluto was preceded in the E.C. Segar strip, Thimble Theater, by the Sea Hag, who remained Popeye's key adversary for many years-- at least on paper.
The Sea Hag first appeared in 1929. She claims to be the last of the witches, and uses her ship, the Black Barnacle, to commit acts of piracy and search out mystic artifacts. She wears a hooded black robe and has a pet vulture named Bernard. For a time she commands an army of "Goons," including "Alice the Goon," who has managed some place in the popular imagination. The Sea Witch has enslaved the Goons, however, and Popeye later encourages an Alice-led rebellion that frees them from her. The Hag presents the pugilistic Popeye with an interesting challenge; he refuses to strike her on the grounds that he won't hit a woman. On more than one occasion, however, an enraged Olive Oyl has successfully duked it out with the Hag. Indeed, we might say that she is initially Olive's enemy, since a lovesick Sea Hag originally targeted Popeye's girlfriend in order to remove the competition. She still harbors an attraction to the sailor man, and some of her later attacks are those of a spurned would-be lover seeking revenge. Over time, she simply becomes an enemy.
She has fared less well in the cartoons.
The Fleischer Brothers first animated Popeye in 1932. At the time, Bluto happened to be the adversary in the strip, so Bluto made his way into the cartoons. Whereas Segar never expressed any interest in reusing the character, the cartoons, which tended to be formulaic in a way the original strip never was, made of Bluto an all-purpose villain, and he appeared in most of the Fleischer Popeye cartoons (1932-1942). Later cartoon studios followed the Fleischer's lead, and kept Bluto as bad guy. Cartoons are kinetic, and Popeye will hit a man. As the strip transitioned from Thimble Theatre to Popeye, it followed the lead of the popular cartoons, and Bluto became Popeye's principal enemy.2
Bluto, curiously, later became connected to the Sea Hag. In the 1960-1962 cartoons, "Bluto" became "Brutus" because of mistaken legal advice; Bluto was so associated with the Fleischer and later Famous Studio cartoons (now owned by Paramount), it was assumed they owned the rights to the character. The new cartoons renamed him Brutus and made him chunky rather than muscular, in the hopes the changes would fool the lawyers they feared might come after them. The new name lingered for a time in merchandising and in comic books. While most people don't distinguish between Bluto and Brutus, some later comic and comic strip adaptations indicate that these are two (at least) distinct individuals. At various times, Brutus has been Bluto's brother, a series of wannabe pretender Blutoes, and the Sea Witch's son. In that guise, he is also called, at times, "Sonny Boy."
Not until the 1960s did we see an animated version of Popeye's old witch. She continued to appear in cartoons from the 1960s and 1970s, turned up in the 1982 Popeye videogame, the 1987 tv series Popeye and Son, and the 2004 feature, Popeye's Voyage: The Quest for Pappy. Different actresses have given her voice at different times. Most famously, Kathy Bates voiced her in the 2004 animated film. She has also been a mainstay of various Popeye comic books. As Popeye's presence in the pop eye wanes, however, the Sea Hag recedes from the public imagination.
1. *sigh* Really? You thought that Popeye's was just a fast food chain?
2. In the original run of Thimble Theater, however, Bluto only ever appeared in a single storyline.