I have blogged before about how the Fighting Fantasy series of gamebooks had a massive influence on me as a gamer. Of nearly equal importance is the Lone Wolf gamebook series by Joe Dever.
The major difference between Lone Wolf and Fighting Fantasy is the former's emphasis on the continuing story. Where every FF book was stand-alone, in Lone Wolf you carry your character forward through the books, keeping your stats and abilities, and any equipment you've gathered along the way. You can play each book as a stand-alone as well, but in general you'll be better off if you've completed the previous installments.
The story is fairly basic yet compelling. Lone Wolf is a low-ranked member of the Kai Lords, a group of warrior monks with mad skills and psychic abilities. They've all gathered together for the annual Feast of Fehmarn, and that's when the evil Darklords of Helgedad make their attack and wipe out the Kai. With the Kai out of they way, the Darklords are all set to conquer the world. Except - Lone Wolf survived. As the last of the Kai, he has to reach the King and then find a way to defeat the evil armies. From there it branches out into tracking down a war criminal, investigating a missing gold shipment, a diplomatic mission, and a bunch of other stuff that gets more and more epic as time goes on.
Besides the gameplay, which is about as good as gamebooks get, Joe Dever's Magnamund is an excellent example of a fantasy world created using very few of the standard elements. You won't find orcs or elves in Magnamund (though you will find shotgun-wielding dwarves in flying ships). It's a great setting that comes more and more alive with each book.
The best part? The majority of the series is available for free right here. Joe Dever has very graciously made the books free for download on the internet, and there's even a lovely interface so you can play them while on-line. If you've ever enjoyed Choose Your Own Adventure style books, or any other gamebooks, you should give it a go. They're pretty awesome.