Well, you have to chose, i am afraid - you either get a linear (or semi-linear game), and a good story, or you get a sandbox-style gameplay with a lot of freedom, but the story will lack the dramatic pacing.
If you want the opposite side of the spectre, try Dwarf Fortress - the adventure mode and the Legends provide hilarious emergent stories, but the game is not very accessible. Also, GTA games offer a lot of freedom with hilarious story bits, and I consider the games very well designed.
An old game inspired by the Gibson's classic called "Neuromancer" comes to mind - the game is very old, but the gameplay was excellent, you were a hacker in the cyberspace, the game took place both in the real world, where you could purchase components for your deck, implants, or even sell an organ or two when out of cash, and in the cyberspace, where you scoured for critical information, hacked ice defenses on databases, fought AIs, etc.
But if you really want relative freedom, immersive story and clever puzzles, I recommend to forget about graphic games and try modern text-only interactive fiction - anything from Andrew Plotkin like So Far, again Tangle in the Web, or Galatea, Photophobia and others. The interpreters and games are free.
