Depends on the path a new player takes determines what enemy fleets they encounter. Some of those paths do have natural progression towards higher difficulty. I will also note if a player takes the suggested Hegemony commission path after the tutorial, then there is a high probability that they'll be hostile to another major faction like Tri-tachyon, which can provide some interesting fights of various scales (Skathi typically doesn't have very large patrols, and are faction fleets) relatively early on. As well as some really hard fights if they go to Culann.
Anyways, Derelicts do naturally scale up over time. The more you do, the bigger they get, and at some point, a solo frigate isn't going to cut it against multiple capital Derelicts (at least for a new player, lets ignore Afflictor silliness). So there is some progression in the exploration and colonization path, which you describe in your progression. I just don't see 3 Derelict frigates as being the same difficulty as a Derelict fleet with 3 Capitals, 4 Cruisers, 6 destroyers and 6 frigates, for example. That looks like progression to me.
Also, contact bounties and intel bounties do start with small pirate fleets, but will transition into faction deserter fleets, which are essentially faction fleets that you're allowed to beat up without penalty (and in fact pay). So I think someone seeking out combat for pay will typically encounter Pirates in Corvus -> intel or contact bounty fleets (pirates) -> intel or contact bounty fleets (deserters/mercenaries) -> high end contact bounties (Ordo bounties, Tesseract). And those bounties do follow a progress, from tiny 40k fleets, to slightly larger 80k fleets, to 120k fleets, to capital containing 150-200k fleets, to mid-sized fleets at 250-300k, and really packed fleets in the 350-400k range (this in intel bounty payouts, as opposed to the high contact bounty payouts). Now the rate of that increase can be argued over whether it is optimal or not, but I don't think you can say there is no natural progression there.
Although for a brand new player, I always recommend running through each of the main menu missions at least once, which also follow a difficulty progression. They don't necessarily need to be beat all of them, but just get a feel for combat. Although being able to beat at least the Medium difficulty ones means they'll have a much better time in the campaign.
As for fleet composition, that would be best introduced through the mission system on the main menu I would think. No risk involved in trying the ships and builds, and the opposition is totally controlled as opposed to campaign chance. I think a pass on sprucing up the main menu missions is probably needed at some point before the 1.0 release once the game balance is finally settled and more ships aren't being added. At that point I'd love to see all the fleet types represented there. Some already are.
For the greater Ludd introduces carrier fleets.
The Wolf pack introduces fast high tech ships in a, well, wolfpack.
Ambush introduces a phase fleet.
The Last Hurrah is supposed to be a Persean League fleet against a Hegemony battle line. The default ship builds probably could be updated to modern Persean League doctrine with DEMs though.
And Forlorn Hope introduces soloing fleets in a super ship.
Admittedly the missions don't introduce skills, officers, or s-mods, but I feel like understanding the true combat basics (speed, range, flux, damage types) before moving onto campaign progression mechanics is best. If you discover you like large missile ships from the Last Hurrah (like the Conquest), then working towards the Missile Specialization skill makes sense once you're in the campaign. And the campaign does give you a level 1 officer as you note. Now maybe there needs to be a popup describing how you level them up the first time they go up a level, and a brief pop-up the first time you dock at a world with an officer for hire, directing you to talk to them. Maybe even a pop-up the first time you go to the fitting screen to describe the green button on right, which hints that saving OP by building in makes the entire ship stronger (although I would think that is pretty evident the first time you try it).
But I don't think a new player needs a full level 5 officer and fully s-modded ships to learn that officers and s-mods are good. Just a bit of sign posting and letting them try.
