Jim Henson's "The Coffee Break Machine" (1967), a skit in an IBM training film, was the first appearance of a proto-Cookie Monster, then green, who evolved from a puppet named the Wheel-Stealer. (A slightly different version of the clip appeared on the Ed Sullivan show that same year.) From the Muppet Wiki:
A proto-Cookie Monster wanders upon a talking coffee machine that has been set in "Auto-Descriptive" Mode. As the machine describes its parts, the monster eats them. Once the machine is finished, the voice of the machine from inside the monster tells him that he has activated the anti-vandalism program, which harbors the most powerful explosives known to man. The monster instantly combusts. The version on the Ed Sullivan Show is slightly different; in this version, the machine itself is an explosive device.