A lot of the disconnect comes from the stupid and absurd skill DC's you see in modules and even in the PHB. When you put DC 30 locks in first level adventures, it only shows you either don't know anything as a module writer, or you really wanted to say 'the pc's can't go this way'.
Another disconnect comes from forgetting the metagaming context that surrounds a lot of D&D. If you make things too easy for PCs - and most skill checks in the real world are actually pretty simple - they run roughshod over the system and have their characters do things that people just don't do; they make them behave like robots or vending machines instead of characters. Some of the craft times are in there simply to foil that, and should not be taken all that seriously. Also, metagaming niche protection gives us Class Skills. Most second generation d20 stuff does away with class skills for this reason.
I would say from the anecdotes that most of them had a single level of Expert and a single level of Fighter, and good stats (which we would of course expect from a Marine). Marines and some other service people are probably the only people in our society that approach what PC-grade person is like: dedicated, resourceful, good stats, etc.
But we can make a good case for Bob the 18-yo Marine to be a 1st level fighter. Why? People keep forgetting about Take 10 and Take 20, and that at first level you get that big x4 skill multiplier. A Marine probably has at least a 12 int, giving him 12 skill points at first level. The only thing that screws him is the class skills for Fighter.
(Technically though, Bob the First Level Marine has come up in our modern world, which has such a huge degree of free time compared to the middle ages that it's like a different planet. People have way, way more time to learn and be exposed to different skills in our modern world. Bob should be a 1st level Strong Hero or Tough Hero, which gives him another skill point x4 AND a better class skill list, which includes Repair, Language Skills, and the Knowledge skills).
12 skill points go a long way, especially when you're talking about the ability to Take 10 or Take 20. Most skills can be done untrained, too, even the crafting skills. Tearing apart most things mechanically, provided that you've been exposed to such things? Average skill check. That's a DC 10, and can be done untrained. Take 10 or 20 on it, as most people do, and boom. You're an expert car mechanic. And these guys have tools, and probably a sergeant around to tell them the quirk about this particular type of gizmo; tools and Aid Another add into that roll as well.
Indeed, most people forget that line that if you're not in combat, you can perform most skills perfectly well, enough to earn a living, without having ranks in that skill. If you have even 1 rank in that skill, like Craft or Perform, then you can do it well enough to make a living at it as long as you're not in extreme time pressure.
So, Bob the Marine, fresh off the Ohio valley farm: Str 14, Dex 12, Con 14, Int 12, Wis 12, Cha 12. Spending his 12 Skill Points, we get: Craft (Mechanical) 1, Climb 2, Knowledge Nature 1 (2pts)", Survival 1 (2pts)*, Swim 1, Perform 1 (2pts), Prof Skill (MOS) 1, Prof Skill (Farmer) 1, and he comes with an extra language because of his Int.
With Take 10 and Take 20, that's enough for him to do all the things SHARK talks about above. He can play a guitar (+2) well enough with most rolls per day to earn more than an unskilled laborer earns in a week, He's woodsy-wise and can answer most questions about basic survival plus survive (hell, thrive) out in the woods indefinately in a loincloth, his basic charm and charisma is more than enough to be gracious at a party and make a good presentation on the drill feild, etc.
*(Again, the d20 Modern Knowledge catagories make more sense for us, here; he'd have Know: Pop Culture and Technology; he'd also get Survival as a class skill from the Rural Occupation he's had since he was 15)
You can solve pretty much every problem with skills in D&D with one simple house rule: Everyone gets a level of Expert, letting them pick 10 skills and 6+int points, x4 at first level.