As far back as the original game goes, a starting fighter was a veteran with all that this implies. He/she has been battle tested and seen action. Every level thereafter added to this capability over the ordinary man. A 4th level fighter was a hero because he/she could fight with the power of 4 ordinary men alone.
I love the old level titles. In 1e, the 2nd level fighter is back to just a "warrior", then they all use swords, as you note they're then upgraded to hero, then become merely swashbucklers.
First level for the other classes were Acolyte, Aspirant, Runner, Prestidigitator, Rogue (Apprentice) , Bravo (Apprentice), and Novice - which hardly sound experienced. Granted, looking at the chance 1st level thieves had to do anything makes apprentice seems right for them.
---
The 1e DMG has some rules under Mercenary Soldier in the Hireling section.
* A Captain is a 5th-8th level fighter (40% are 5th level, 30% 6th, 20% 7th, and 10% 8th) - they control up to a score of soldiers per level + one lieutenant per level (excluding the needed serjeants)
* A Lieutenant is a 2nd-3rd level fighter (70% 2nd level, 30% 3rd level) - they control up to 10 soldiers per level (adding to the total led by the captain, and excluding the needed serjeants) and have one extra serjeant per level beyond that that don't directly command troops
* A Serjeant is a 1st level fighter- they can control up to 10 soldiers each (sometimes as few as five)
* A standard soldier is a 0-level man-at-arms.
That means an "average" mercenary company at full strength (e.g. with every commander maxing out their command skills) has around:
1 - 6th level Fighter (Captain)
2 - 3rd level Fighters (Lieutenants)
4 - 2nd level Fighters (Lieutenants)
40 - 1st level Fighters (Serjeants)
260 - 0-level Men-at-Arms
So, roughly 0.3% are 5th-8th level, 2.0% are 2nd-3rd level, 13.0% are first level, and 84.7% are zero-level.
For some reason, none of them are allowed to advance in levels, so I'm not sure where they come from. Apparently 4th level Heroes aren't allowed to be mercenaries at all.
---
The 4e Monster Books seem to give a completely different impression with the CRs of the various types of humans - is a town guard 4, a gladiator 10, and a pirate captain 14 or something like that? (I never remember for each edition what the CR to level conversion is though.)