Super Mario Lost Levels was designed to appeal to more experienced players, or otherwise anyone who seeks a challenge. I would not count it as a testimony of how hard Mario games were back then as it's more of an oddball even against its contemporary 2D Super Marios: Super Mario Bros. before it was considerably easier, Super Mario USA pursues less platforming precision and more "exploration" (inasmuch as running around plucking every tuft of grass to get vegetables, potions, and shells can be considered exploration) and Super Mario World reserves much of its difficult levels for the extra final world, much like how newer titles get around really. Let's not even talk about Super Mario Land and especially its sequel--no other Mario game will ever reach this level of streamlined design again.
I deliberately left out SMB3, not because it would stain my argument, but because it's so poorly designed I'd call it cheap more than difficult.