Another alternative, if you are looking for a more "seamless" look/feel approach, could be to enter some kind of warp sequence or such. This could provide an opportunity to make the act of traveling it's self a part of the gameplay AND you could add in a set of new gameplay that takes place in between locations should you want to go that way too.

Games like Ratchet & Clank Future do this and it's quite fun if done well.