Non-Linear: If you always start on level one, everyone has to do that, then level one unlocks levels 2,4,6 say which you can then choose from, level 2 once complete unlocks 3,5 and level 4 unlocks 5... etc etc, this way you can work your way through the levels in certain orders but give it some kind of story so you don't have to do all the levels say, and you can choose what order you do them in to a certain extent. Dicuss...
This could be done by allowing multiple exit and entry points.
You can simply store the spawn point of another map as the destination.