C-3PO and R2-D2 appeared in two episodes in the 1979-1980 season.  All the "Street" footage of one of those episodes has been put up on YouTube.  It should still be there, though I wish I had the link on hand.  (It comes from an unedited studio tape, so you see director's markers and hear the actors mumbling in the background)
 
A few of the scenes taped for those episodes were recycled for many years after that as inserts.  The only one I remember seeing as a kid was the one where R2 falls in love with a fire hydrant 

 .  
 
So for all the years after those original episodes aired, kids would see the re-used inserts with the Droids,  without any explanation of what they were doing on Sesame Street---just like all the other unannounced celebrity cameos. 
