I think that there should be more of a story line to each map. I have a great idea. What if there was a person on the island before you spawned the first time, and all that is left of him is his run down abandoned shelters that would be scattered across the map, but hard to find, with a chest with a journal entry in them. There could be 10 in all. Each will have a number on them representing which one you have. They could all have to do with his expiriences of surviving. Also you could see in them how he slowly starts to go crazy. And it gets to the point where he gets paranoid. There could also be a legend that he still exists as an outcast off in the distance sometimes. This could bring in the "Herobrine" myth to an actual twist in the game.
Abandoned shelters