Another update (?) sidenote:
I'm also upscaling the "ugly" Battle textures... well at least they look ugly to me.
This is early WIP but the upscaling shouldn't take as long as the backgrounds, so maybe 1 week if I've decided on my filter pipeline.
I'm also touching on those ugly low res character textures and weapon texture as well.
Let's see if I can even do something with the worldmap textures.
If you find yourself running into lines between textures after you upscale, you might need to make them seamless. I did this with masking seamless textures over the existing ones and/or clonestamp tool to each tile by hand (old school way) for my FF8 maps. Unfortunately, the FF8 UV's are bunked on the PC version. Hope FF9 fares better.
Turn off any filtering first just to make sure, before you go re-seaming everything though... linear filtering, etc. can cause extra edges between seamless textures on atlases.