I agree the History of Dance episode was on par with lesser episodes from other seasons, but the puppet episode was godawful.
It's especially painful for that episode to be bad, because after the Claymation episode, you have to think if they had a puppet episode in the first three seasons they would have nailed it.
I know I'm on a 'South Park reference' kick right now, but I'm going to make another one. In the mini-commentaries on the South Park DVD, the South Park creators often mention how they insist writers make jokes that are references to the story and the characters instead of the traditional sitcom-style jokes that are just one liners that have nothing to do with anything. Season four has been all bout those sitcom-style jokes, one liners that have nothing to do with anything. They toned down all the characters and made the humor more sitcom style, more based on one line quips.
And the musical parts of the puppet episode forgot to make fun of the style they were emulating.