Honestly, I alwaysd thought of Charlie as being an Anything Muppet humanoid, not a monster (though I guess a monster would be more likely to tolerate Grover's mistakes and customer complaints).
I think the orange monster mentioned is the manager seen in the "service bell" sketch, but he's named Andre. And in that sketch the set looks different (more fancier than the usual Charlie's Resturaunt set... Not sure how to describe it). And at the beginning of that sketch Mr. Johnson comments that the place had changed since his last visit... But I don't know if it's specifically referred to as Charlie's Resturaunt in that sketch (I guess they didn't want to actually show Charlie and chose to mention the manager's name to avoid "confusion").
The "full and empty" sketch is from the second season (Cookie Monster looks the way he did in the first two seasons), and I think the "Waiter Grover" series began in season three (Sesame Street Unpaved refers to the "alphabet soup" sketch as the first of them, and the third season premiere, featuring the alphabet soup sketch, is the earliest-known appearance of any waiter Grover sketches). The name was probably arandom name, before they decided to mention "Charlie" of the restuarant.
Another thing I wonder: When was that restaurant first referred to as "Charlie's Restaurant"? If not for the title would we have thoguht of Charlie as the owner, as opposed to just a cook or other restaurant employee? Resturants have other cooks besides owners, after all.