i think the zelda games did these things well, most notably majoras mask and the original nes one.
i say this because you felt like you were getting somewhere as you played, but not in the same way as the RPG(insert japanese crap here+roman numerals). in the nes zelda you were free to roam anywhere you wanted, limited only by your skill as a player. if you wanted you could accidently walk into dungeon 4 with the wooden sword, and beat it. thats what was great about it, you were exploring, the game was a map with things to help you along your way, and you had to achieve a goal in the end, but getting there was done on your own time and if you wanted you could spend hours exploring and never finding a dungeon. this is the type of gameplay we need. now of course like any nes game it has its shortcomings, like every enemy was sorta the same, it had pallette swaps, but the basic prinicipal of its gameplay was very fun, if youve never played it, give it a try
http://nintendo8.com/game/810/legend_of_zelda/
now if you were paying attention i mentioned majoras mask b4. why? well because it too had very good and original gameplay elements. although it lacked the open worldedness in its story driven game it still had the feeling of an open world, as did ocarina of time. but it had a whole side story which once the game was completed was a whole new challenge on its own, finding all of the masks. you needed to talk to people on certain days, go places at certain times and it all felt difficult, but it made sense. the limited time system in majoras mask is what made it hit or miss for most people, i myself loved it, the days effected peoples attitude towards what was going to happen, and everyday you felt their spirits drop as the moon moved closer. it was saddening somewhat. it gave the game a dark feeling, you felt the npcs to be real people. it was an overall immersive experience.
so to conclude all this, id like to point out that if you want story in your game, it should always be secondary to the gameplay, you also need to make it part of the game rather than cutscenes and such. majoras mask used a story element as a driving force behind its gameplay, but it never really got in your way aside from one or two critical story cutscenes (which were enjoyable since there were few of them). your game should also feel original, make the player not know what they should expect, and adapt the gameplay because everythings does and will get stale after too long. let the player make some of the choices, but not through a yes/no type path. create alternate endings, and let players make their way alond those endings their choice instead of yours. linearness kills a game, thats why most ubisoft games get that tedious feeling to them even with very unique gameplay elements (prince of persia?). alter level design and puzzles as much as you do gameplay.
thats my two cents