I'd say that different game modes are the way to go. There's the story mode, then there's a freeplay mode. Of course, the freeplay would have to have a pretty good amount of story, and the story mode would have to have a pretty good amount of flexabillity, too. What this is really about is balancing how good it will be the first time around and how much of that is still worthwhile when replaying. Of course, if it isn't good at all the first time around it will still be no good replaying ;).

There are already story driven games which are open ended, the problem is all the ones I've played that have done this arn't too fun. Open ended games don't give the player much, they do get bored, GTA I'm bored of, every game gets boring, so an open ended game can never suffice a player's need 'to game', focus on the story more, then add numerous challenges which the player can do before he/she completes the game.

E.g FF7 you could fight sephiroth, but could fighted ruby, emmerald weapon, they were challenges players had to play much more to do. Make sure to add many bonuses which are optional, maybe new attacks, or more levels, maybe mini games.

What you could do is use the open-ended portion of the game to fill in gaps in the story. For example, you want to overthrow the tyrant who killed your friend (lame story, I'm sure the professional writes would come up with better ones), but the story only sets up the basics: the objectives, what happens once they're achieved (more story), and maybe a few story-related one-time things in the middle. How to actually do it is up to the player, and in addition to the obviously different ways to assassinate a leader, there could be many factors affecting how you played, like if you were unwelcome in that town (strongly opposing factions), so you couldn't just walk up to his manor and kill him. An alternative in this situation would be rallying a sizeable group of pirates to take the town by force, or trying to cross the whole town undetected. Some players could be defending the town against this kind of attacks, making things more interesting; all of the game's systems would be playing a part on this, it would be cool to see the economics and opposing factions creating a stronger dynamic whithin the story.

The idea would be to use the open-ended gameplay interleaved with the story, allowing the player a lot of freedom to do things as he sees fit, but connecting these "meaningless actions" through a story. The emphasis is on defining broad goals and letting the player elaborate.