A quibble: 4e paladins are more like 'beat-on factories'. Their main ability is to take an enormous amount of damage each fight.I'd prefer a knightly paladin to a god-powered beat-down factory, but I understand that the latter is probably more generally appealing.
As for worst class... can't say yet. Our cleric and warlock players were nonplussed by their characters, but, coincidentally enough, they were also nonplussed by the system in general.
I'm wondering if the later controllers will make the wizard uninteresting. So far our wizard player has no complaints, but he also has a terrific character, in the non-mechanical sense, so that's probably influencing his opinion.