I really tried to like Valhalla, but the combat is so horrible compared to the previous Assassin's Creed games, which for me was always what I loved about them.
My personal favorite game of all time still goes to Dishonored (all of them). The story is amazing and you pick your own style of gameplay with the powers that you choose.
Ghostrunner is also a nice game, where you'll keep trying to perfect the way you move through the story. It's also nice, because the story just kind of unravels mainly in the background as you play, not leaving you with all that many cutscenes.
Other honorable mentions: Batman (Arkham Asylum, Arkham City, Arkham Knight), Saints Row (best played with friends), Vampyr, Ghostwire.
Then there's the real story driven games: Sea of Solitude, Before Your Eyes (you need a camera for it), A Story About My Uncle