As I recall games use to be about gameplay and less about story.
That's never been the case.
The problem is that developers never had the ability to introduce story into the game's environment. The NES was a revolution as they could suddenly achieve really detailed story experiences, but even before that developers were struggling towards story; every game had a giant manual which covered the backstory of the world and the player's quest, there were many text adventures for the PC and gaming mascots were always given their own giant stories so as to be more inviting for kids.
Pong was 100% game.
Pong was, at the time, a detailed simulation of ping-pong/tennis and the story was about two players coming together to duke it out to see who was the best.
Super Mario was 99% game 1% story
You clearly never read the manual that came with the retail game.
Why do you need stats and progression for games? Why do games need story?
Because games are about the learning process. Games are about becoming better at things. The very nature of "playing" is that humans who play are trying to identify what they can and can't do. When kids play, it's more than just loving around with some toy cars; it's them learning how cars work, how their own bodies are capable of moving and how to make interesting stories.
Story, since the time of the caveman, has always been about the passage of knowledge; every story carries meaning which is ideally passed on to the audience. The reason story works best for this is because we connect better with emotional feelings than we do with hard facts or statistics, and story is designed to evoke those emotions which we're much better at remembering, which in turn helps us remember ideas which the author wants us to know and understand.
If a player is able to see that they're progressing, they become more entwined with the experience and their sense of enjoyment increases, as the body produces more dopamine as a reward for continued progression. I'm sure even you've felt happy or satisfied when you've managed to get something awesome done in a game; that's your body saying "well done for advancing and becoming very good at this activity."
Pretty sure NMS is more of a game than any loving game out there currently.
Please provide evidence for this.
I don't count "button prompt cutscenes" as gameplay. I'm looking at loving god damn Tomb Raider when compared to the older Tomb Raider.
That's not the meat of the gameplay for that game, though. They are simply trying to make the cutscenes a bit more engaging by adding some challenge to them, instead of making them things you snore through. Game Developers are always working on new ways to weave gameplay and story into each other; it's not the best way, but it is a start.