They never had a narrator, unless you count Gonzo and Rizzo in MCC... and that was just an excuse to get more Muppets into that movie. I don't think they'd really need one, since all the other films were quite fine without them.
I know that Muppet Christmas Carol was the only one to have narrarators, but I thought putting a narrarator in a Muppet movie would be an interesting twist. Though I wasn't thinking in terms of how Gonzo and Rizzo were used in MCC, more along the lines of Sam's narraration of Muppet Snow White, sort of a cross between the linking footage of Children's Songs and Stories with the Muppets and Ernie and Bert's interruptions in Elmo in Grouchland.
Now that I think of it, Kermit sort of narrarated Kermit's Swamp Years (I know you've said you've never seen it). He appears as adult Kermit at the beginning and end, sort of like his narrarator roles in Emmet Otter's Jug-Band Christmas and The Christmas Toy, and I'm pretty sure he does some voice-over narraration (I haven't watched the movie in years and can't quite remember).