I think that instead of, or perhaps in addition to, the reduction or abolition of anima, the reduction in the number of teleportation destinations would help a lot.

FFXI had about 6 teleportation destinations in its prime: Dem, Holla, Mea, Altep, Yhoat, and Vazhl. All of these except Vazhl had a chocobo renter right there, allowing you to teleport to one of a few central hubs then rent a chocobo to get to where you were going quickly and safely.

The benefits of this system: Reduced travel time without eliminating it. Left a little bit of a timesink there without causing frustration to players. Allowed players to learn the lay of the land better, making them more at home in and attached to the world. Created landmarks which every player could instantly recognize: the Crags.

Now, there were also Outpost warps for every region in the game, but those required decidedly more work to gain access to.

My suggestion for XIV:

Create some reason for the Aetherial nodes and the aetherytes in each camp to experience a large loss of energy, preventing a strong enough connection to players to teleport directly there. Add massive growths of crystals in each region, only one or two in each, which become the hubs for teleportation. This way we can keep the camps with their aetheryte crystals as sources of Guardian's aspect, HP/MP recovery, etc, while having a reason that they can't be teleported to any more. Allow us to rent chocobos from these crystal hubs and voila, I think most people will enjoy the world a little more.

I think with the deaspected crystals popping up all over the place, this would be an excellent way to introduce this change fluidly.