Don't trick me into saying it's like Spore
I would like to compare it with what
squidi talks about here. Squidi leans alot on HOW to create a distributed world and how to link them together and that's where he's dropping the ball in my opinion.
I would have one server that keeps the integrety of a grid of screens intact. This server works only as a tracker that stores links to each screen. It might sound crazy to go as deep as hosting individual screens but I really think it needs to be extremely distributed. This server could have a cache of game data that is updated daily so you still can play the game if some hosts are down.
I would store some game data in image files so that anyone could create a screen with a simple drawing program. Kind of like how easy it is to create a webpage with notepad. There's no need to store binary data in these images. I've tried before to store scripts in image form using symbols but that too feels like a stretch. Most likely XML would be a great way to store data in too since it can be easily created and easily verified. This would also make it possible to view the whole map using a browser.
I think Legend of Zelda is a great game to apply this to. It needs to be a simple game with simple game mechanics, then over time one can introduce more and more features.