The idea I'm currently running with is to have a hub area where you buy stuff and whatever, and then to also have several large areas with smaller missions. There'd be like five missions per area, and they'd each have you going in different directions with slightly altered environments. The closest thing I can compare it to is Mario 64
So let me ask you, would you play a game like that, or more importantly, do you think you would enjoy it? Or do you prefer a more 'walk from point A to B' approach?
Also, on a more technical note, I would want players to have an open-ended choice as to which areas and missions they do. Considering that, I'd curb the difficulty by having it so that if you left a mission from the first area and came back to it when ur level 99 you'd still be challenged by the enemies there, rather than just mindlessly plowing through them.
Wadda ya think?