I think I may know when Slimey first debuted.
Back in the early to mid 1970's, there were a number of episodes which focused Oscar tried to isolate himself from the others in one way or another, or in some cases, silence those around him. In one such episode from maybe 1972, Oscar decided to have a padlock installed on his can.
I think it was that guy from the Fix-it Shop from the earlier seasons (Ralph or Rafael?) who installed a latch and a lock on the lid of the garbage can.
Oscar was standing outside the can, watching and directing the installation process, and I'm pretty sure one or more other adults were also present. Once the lock was in place and secured, Oscar demanded "Now open it."
The Fix-it Guy thinks for a second, then says to Oscar "Give me the key." while holding out his hand.
Oscar: "The key is in the can"
The Fix-it Guy can't open it now of course, and Oscar decries "You locked me out."
After considering ways to forcibly pry the lid off, Oscar announces he has a better idea: Slimey. When the adults want to know who/what "Slimey" is, Oscar tells them about his pet worm. He then called toward the can for
Slimey to grab the key which he left on the coffee table. We then saw
the worm make his appearance under the crack beneath the lid, along with what was probably a skeleton key.
True, I can't say with absolute certainty that this was Slimey's very first appearance. But as I've said many times here, I watched the show quite religiously the first 7 odd seasons, and this was the first appearance of the earthworm that I ever encountered.