After I started FFXIV, I picked up Bravely Default (a very Final Fantasy-like game from SE) and was struck by how much time I spent wandering around the overworld! It was somewhat tedious (especially if you weren't excited about the frequent random battles) but also immersive because you actually felt like you were actually going to the Temple of Wind.
There's fast travel in Bravely Default too...