FrogReaver
The most respectful and polite poster ever
It really depends so much on the exact ability scores and player choices. Most likely, that rogue ends up with +1 or +2 over the paladin. My previous campaign used 4d6k3 and overshadowing there was far more pronounced.
Which CON features are you referring to, for paladin? Do you mean Aura of the Guardian where your hit points would be salient? I couldn't find any others (from PHB and Xanathar's).
Looking at this objection, I feel like there could be another factor in play. My intent with allocate-as-rolled is that players won't have total fiat over class and race, or party balance. They must live with compromises and faults. Even so, it is up to each player what they choose: I think players with high-system mastery and an interest in optimising will not choose a sword bard unless they have the stats for it. Thus the situation one may fear in theory-crafting doesn't arise at the table. Say a player draws DEX 13 and CHA 14? They might choose to play a half-elf sword bard and do perfectly well with it. They won't be as strong as a points-buy character could have been, and that is by intent.
We need to separate the arguments properly. The intent is a weaker party, relative to MM creatures. So if a poster here dislikes that then on the one hand I have no criticism for their choice in that regard, but on the other hand that is not my choice. Therefore this is not something we should argue. The other argument is overshadowing. Even a +2 overshadow is mild compared to that I have seen under 4d6k3. More importantly, in play the raw ability scores are only a fraction of character leverage over the narrative: wise choices and clever use of the resources at their disposal are telling. Does the paladin use her spells and buffs wisely, while the rogue is intemperate?
Don't lump me in with arguing against a weaker party. In fact, I don't think anyone has done that. The issue is simply that mad classes lose a lot more than single stat classes (or maybe I should say dual stat classes, everyone benefits from a good con)
The problem is that when I roll in order, I'm fairly likely to get decent stat I can build around. It much less likely I get 2 decent stats to build around.
That kind of ties into your goal of having players build a character around their stats. But when you realize how that's going to play out you realize there's not really "fair" options per stat. Then there's always the issue of an extremely low con crippling any character out the gate
Going through the classes
(Str Classes)
Fighter: Strength Fighters will likely lose attack, damage initiative and hp but not much else that really matters.
Barbarian: Will likely lose attack, damage, ac, hp
Paladin: Will likely lose attack, damage, charisma bonus to saving throws, spell dc, hp.
Rogue: Will lose attack, damage, ac, hp, initiative
Monk: Will lose attack, damage (more based on multiattackers being impacted by last damage), ac (more based off requiring 2 stats for ac), hp, initiative, stunning strike DC.
Druid: Loses spell dc, hp, ac (however can mitigate most of that by wildshape)
Cleric: Depends on subclass - Str Based loses: attack, dmg, hp, saving throw dc
Wizard: attack, ac, hp, initiative, spell dc
Sorcerer/Warlock/Bard: All lose hp, ac, attack, spell dc (popular melee variants of these classes lose far more)
Classes like the monk really get hit hard. Classes like the fighter barely notice. On a side note if someone was to roll say a high dex and wisdom, they could make a monk that really overshadows the rest of the party.
I'd say any strength based class is playable with a high str.
The rogue is the only dex based class playable with a high dex (dex fighters also fit here)
Shapeshift druids can be played by any stat spread
Clerics work well as long as you take a heavy armored variant and have a high wisdom
Wizards lose some, but as long as their int is high then they still work well
Sorcerer, warlock, bard all work fine with a good charisma
So I guess you can make this work - but you lose out on a lot of the interesting gish type classes. Monks flat out lose out unless someone rolls super lucky. Multiclassing will be much harder (might be a good thing).