I'd highly recommend Outer Wilds if you want a really interesting story.
It's a puzzle game, but unlike traditional puzzle games, outer wilds takes the approach of open world exploration to tell its story. The puzzles themselves aren't complex, but relate to the story itself.
The world is set in space, flying from planet to planet to figure out whats going on within the universe.
It's definitely the first open world game where I've felt like the sky is the limit for where I can explore within its mini solar system.
As a plus the music is fantastic, and the art style is good too.