Guild Wars 2

In addition to the hearts and events in a map, add a story line for each map or certain maps. This story would have take the player from place to place through the map helping NPCs and showing the player the history of each map, how it used to be, what these ruins were, what happened etc. Give the player rewards at the end of key steps to the story line and a special reward at the very end of the chain, similar to the player story line.

This would add a sense of direction and history to each zone while still having that great sense of exploration you get from finding random events and completing the hearts on the map. And everyone loves rewards.

Does this sound like a cool idea?

The idea is good. They really need to work a lot for the storyline because it is interesting and varied only till the characters get in LA and join a Faction. From there its just the same story for all characters only with small different roads.
From lvl 30 to lvl 80 its the same story, no matter what faction you choose. This really needs to be changed.