With months upon months of hacking, tweaking and even a small amount of spriting, Zeemis proudly presents the 'FFIV: The After Years' tileset for 'FFVI'. This tileset overwrites the existing tileset if you choose to apply the patch.
I used Yousei's SNESPal and YY-CHR to make this happen. I even used FF6LE to fix tile collisions and any form of a tile anomaly so that if you're not a hacker, you can still experience this patch by playing through a normal play through.
This is only for the World of Balance, it does not affect the World of Ruin at all.
This has been submitted to RomHacking.
This patch was originally developed for Final Fantasy III SNES 1.0, I'm unsure if it works with any other versions.

Two screenshots for comparing the old to the new, make sure you zoom after the image loads. They are both full blown world maps, so they're big images.
New Overworld Tileset.
Old Overworld Tileset.

-=Download=-

Thanks.
Here is the official submission:
http://www.romhacking.net/hacks/824/

That looks amazing!  Might I suggest using the FF4 underworld tileset as a starting point for handling the World of Ruin?  (You'd probably want to recolor some things from their FF4 appearance - maybe use overworld water but recolored purple alongside the underworld tiles or something?

Is that shrine below Zozo used?