Interesting question, and I like your examples! Indeed, there are a few different ways to connect the world.

For me, some kind of interconnected world seems natural, a continuous world where you can go anyplace you like. The question is rather how to travel. I first thought about driving/flying from place to place, but there is a risk of the travelling either gets dull, or it is so short distances that it doesn't really count as travelling (can be helped by some accelerated mode or "space warps"), or the transportation is spiced up by combat, which would then have to be so integrated with the game that it controls what the game is really about. Hm...

Now, I consider some solution more based on "portals", moving instantly from location to location, possibly with some animation between to symbolize the actual travelling.