I find the Mega Man series of games has usually been a mix of all 3. Select any stage, and after finishing them, you are given a set of more difficult stages that are linear in progression. Seasoned players have figured out there's sort of a puzzle to the best order of beating the bosses/stages, as the order of weapons you obtain present better options to tackle future stages. If you can work out a challenge based around the order in which the stages are beaten, this could be a fun way to play the game.
In other cases, the game has no apparent barriers to let you explore the whole world at first, but the extent to which you can explore it is limited by your character's abilities. This is common in RPGs, but also in Metroid/Metroidvania type of games. The world should be set up in a way in which the player would have to figure out where to go next, but without getting lost. If the process of elimination is made easy for the player, he would know where to go next and incidentally obtain an item that will let him pass through to places he previously couldn't go before.
The replayablity of the stages depends on whether or not it is worth the player's time to visit old stages with their newer abilities. You'll have to give him an incentive to go back, either by teasing the player with visible but out of reach areas during the first run, or some storyline component that calls for some backtracking.