they should just have Link get shipwrecked on another island (a real one) thats not too massive in size, but not too small either.
the whole thing should be like one big ass dungeon where you get to explore the entire island (which has no central town/village, but does have NPC's scattered across out in the open or in remote locales), using the weapons you acquire to traverse the terrain. You can have the traditional dungeon themes but mix them up a bit; work them not only into the environment (the island around you) but the other dungeons themselves;
do a side-quest favor for an islander that results in a dam being built in the nearby river, opening up a portion of an underground dungeon. You don't have the right equipment yet so you move on to another dungeon. something occurs which breaks the damn, but that dungeon isn't blocked off, its still accessable from another part of the island, however its now become flooded (creating new puzzles), etc.
Basically this new zelda should bring back the awesome challenging puzzles of old, as introduce some more metroid-like exploration. to be honest, i'm surprised it hasn't happened before.
ps the island setting is just an excuse to get link to take his shirt off again, yum!