It seems appropriate that I should field this question.
I don't know when Gorgon Heap was built or if it was specifically for TMS, but I think he may have been in the background (the VERY background) of the Sex & Violence pilot.
His first TMS appearance was in the episode with Joel Grey. This is the only episode in which he has ears instead of horns. He was performed by Frank Oz, and appeared briefly in the opening number, "Comedy Tonight", and played Fielding the Butler in the Sherlock Holmes sketch opposite Rowlf's version of Holmes, Baskerville the Hound's Dr. Watson, and Piggy's Maid (the latter two get eaten).
Next he was in the Avery Schreiber episode (with horns, now), performed by Richard Hunt, in the Wayne & Wanda sketch "Some Enchanted Evening". Wayne sings to Wanda, and at the end of the second line, Gorgon enters, having misheard Wayne's "you may meet a stranger" as "you may EAT a stranger". Gorgon eats Wayne- in about five seconds, no less!- and a distraught Wanda wails "He said MEET, not EAT!" and starts sobbing, to which Gorgon replies "Oooh sorry!" Why he didn't eat Wanda as well I'll never know, doubtless she looks tastier.
Gorgon Heap got his name in the Vincent Price episode, the panel sketch with Vincent, Kermit, and a Whatnot chef named Pierre LaCousse. After every mention of a dish, Gorgon says "It is delicious!" and eats something, later eating Pierre and trying to eat Kermit. He was performed here by Dave Goelz, I believe.
His look changed twice in the Rich Little episode. He had a long nose to do the "Inchworm" bit (originally performed on "Sam and Friends") with Lenny the Lizard, and appeared as he normally is, albeit without horns, at the end of Rich's interview with the reporters outside the backstage door. From this point on he didn't have horns. In the "Inchworm" sketch, he only makes a few utterances, none of them words, but clearly these utterances (growling, chomping, lip-smacking and belching) were made by Frank Oz.
He appeared one more time, briefly, as the drummer in a monster band accompanying Leslie Uggams' opening number "Hey There Good Times" in her episode of TMS in mid/late Season Three.
Here are a couple of pictures:
http://www.kermitage.com/html/characterindex/tms/characterg.html
http://www.thecapras.org/mcapra/muppets/images/TheMuppetShowAlbum.jpg
I don't know of any other appearances besides TMS. Someone else will have to supply that information.
Hope this helps!
David "Gorgon Heap" Ebersole