Personally think the open world type works the best (totally unbias here) with the king of the tower one in second place (though you have to deal with the fact that it would probably be hard to deal with people cheating to become the K.O.T.T) and I think the level based one with hub would lose part of the charm that games you make like this have of being very real, though a level editor does sound rad.
"to kill more Tyranous kings." I don't know about that, at least if that is the only thing you do. What I think might be cool is that this world is pretty dim and dry like the lower part of "KtK.O.T.H." but after you get to the top of a tower you can let out the life giving water at the top (might be hard to have it pour water of the sides depending on how the tower is made though) and with it life returns to the land around it (and the fog/dust ,if there is any in the area, clears, though as Burace has said the fog kind of stops the player from seeing how cool the area is)
Maybe the area is overcast to start with and you can't see past the cloud layer that the towers go through, so you can still see a lot, but it's dim and you can't see all of the tower till you clear it. Just imagine getting to the half way point, maybe two thirds up, and passing the cloud layer to see a bright clear sky, and once you clear the whole tower you can see that bright sky from the ground around the tower.
Hmmm. You've given me a lot to think about... I like the shadow of collosus + restoring water to the land that was horded by a tyrant idea. It's a simple reason to build many levels, but around an overworld map. Might be a bit ambitious though - since an open world demands a lot more tech, and I am one person.
Also just FYI, the killing of the king is supposed to be like the flag at the end of old mario levels. Just a satisfying finish-line ritual - but everyone was expecting a boss fight it seems :P
Oh I wasn't expecting a boss fight, since there wasn't any combat anywhere else in the game.
Since it just felt a bit less polished since the platforms look a lot better than the sprite stuff and with the more shadow of collosus aspect it feels like a more lonely world (no kings, just towers) would fit better. Also a cool sequence of gears or mechanical parts moving to release the water could also be really satifying and a bit cinematic too.