For the record, I am currently playing a level 12 Paladin with 16 STR and a +1 weapon, and 18 CHA. I probably whiff attacks a bit more often than the Rogue/Fighter with 20 DEX, but overall I don't feel like I'm constantly missing or failing to deal damage.

Sure, Paladin has a higher floor than Barbarian, and my chances to hit are empowered by Bless being pretty much the first thing I do on every serious encounter, but I think Skrum just got "unlucky" in that immediately after respeccing for lower STR, he failed a couple rolls by *exactly* the 1 point he gave up. In the long term, the difference may end up averaging out, and with added sources of bonuses to hit (Advantage, Bless, Bardic Inspiration, Magic Weapons), they'll breach the gap, hopefully.