Personally, I find that even the most successful of games which are deemed to have strong stories often don't. For many games, the narrative is, at minimum, engaging—it isn't really that much of a challenge to provide that much (although crafting a unique story itself is.) To me, there are three things to consider when approaching this topic: writing, storytelling, and the story itself.
As an example, a recent game often praised for its writing is The Last of Us Part II. Is its writing really all that impressive, though? No, not really. But its story and storytelling are commendable, with the former going deep into themes of loss and the moral complexities of survival while the latter structures the game's events in a way which will force players to reconsider their actions for two separate characters with conflicting motives. For other games praised like it, usually there is only one, sometimes two, of those three aforementioned aspects truly worth praising, and it's rare for a game to succeed in all three. With that said, I actually have played Nier: Automata, and I do believe it's one of those rare instances.
After glancing through my list of completed games and pondering about certain items, I think these are the three other games which succeed in story, storytelling, and writing: Kentucky Route Zero, Silent Hill 2, and The Stanley Parable. I'll also mention Hellblade: Senua's Sacrifice as a game I've watched someone else play.
