I had the same impatience with the old Zork-type games back in the day. Harking back even further are good ol' pen & paper RPGs. I only played D&D once in my life (for about half and hour), but some 35+ years later, I decided to give the
Mythic Game Master Emulator a try. It's essentially a free-form adventure prompter. Your story can be whatever you want it to be, but it provides mechanisms to add surprises. Sitting in a coach seat on a 5 hour flight, I found myself chuckling as I went on a little time travel romp. I inadvertently triggered the Battle for the Little Big Horn before landing.
I'm also intrigued by some of the new indie "interactive storytelling" games such as
Fiasco. These are more story focused than adventure. Unfortunately, there's nobody nearby that I'm likely to play with.