Here's the thing.
Even a 5DmkIII only weighs <1kg (~1.9lbs).
A 24-70mm f2.8 L weights about 950g (~2lbs).
Combined weight: ~1.8kg (~4lbs).
An Arri Alexa Plus weighs 8.4kg (18.5 lbs).
A Cooke S4/i 35mm weighs 1.9kg (~4lbs).
Plus you have matte box, filters, follow focus, on-board monitor... sometimes you have on-board recorders like the Codex (1.1kgs/2.4lbs). V-Lock/AB batteries, wireless transmitters etc. Then you have your handles.
That's why if we're hiring for a handheld show, at prep we make sure we have as many lightweight accessories as possible, as even just having a lightweight matte box and follow focus can make a huge difference in weight versus a studio matte box and follow focus (probably about as much as our entire 5D kit above).
Not only that, but handheld rigs for large cameras are designed so they can be balanced as well as possible. When you buy a cheap shoulder rig for your 5D, the camera is probably in font of you, though you
may have something to chuck on the back as a counterweight. If the camera is not balanced properly, it's going to be very difficult to keep it steady and straight, and will start to hurt much more rapidly than a properly balanced camera.
Now, the Alexa's shoulder cutout is not in a perfect spot, but there are third-party handlebar/shoulder pads that can be moved to accomodate heavier lenses etc.
On top of all that, cameramen/women
practice their operating, and work out to ensure they have the strength in their muscles to keep a 15kg (33lbs) rig on their shoulder all day, every day for 3 months straight. Look at any operator's first film and their camera operating will suck big time in comparison to what they're doing now. My camera operating when I first started was pretty average, but I'm pretty happy with it now. And it gets better as I do it more.
One last thing: many times when you see a 'handheld' show, and 'handheld' footage, the camera is actually on a tripod with a really loose head. Modern Family, for example, are huge culprits of the 'loose head handheld' technique. They combine loose head and traditional handheld quite a bit. It's another type of operating that takes a lot of practice (as all operating does), but it's a good alternative to having a huge camera on you shoulder all day. Most won't pick the difference - I've done it myself and only the people on set knew that it wasn't actually on my shoulder.
You'll probably find that the 'smooth' handheld you were seeing was potentially actually on a loose head. Sometimes it's hard to tell the difference between an incredibly talented operator.
Here's a perfect example: