Perhaps an illustration would help explain what I'm talking about.
In the attached image, all the tiles are using the greyscale palette used by the castle wall tiles. This illustrates what I mean by different tiles having different palette indexes. The castle wall sections look correct but the water looks like stone, and so does everything else. Probably what's happening is the map has associated with it a "large" palette of X 8-color segments, and each tile has associated with it a segment index. Like so:
[########][########][########][########]... etc
00 01 02 03
So in the Sylph cave, the palette would consist of various shades of brown and green, whereas in the Feymarch it would consist of various shades of brown and red, but the damage floor tiles would always use, say, palette segment 6, which would be green for Sylph and red for Feymarch. Probably. In reality I have no idea how to figure this stuff out, I'm just speculating.
As well, you can see from the graphic tiles themselves what I'm talking about in terms of having to assemble the actual 16x16 tiles. The game tries to reuse tiles wherever it can, so no doubt there's a castle wall tile constructed by using tiles like so:
03 04
03 04
In "FF4.txt" there's a section of rom from A2000-A5FFF labelled "Town Map Tile Formation Data (*4)" which I initially assumed would list graphic tile indexes in the order they're used to construct map tiles (so for the above example, something like 03040304). However, upon inspection of the data in that section, that's definitely not how it's stored; or if it is, it's not as straightforward as that and there's something more complicated going on in there. For example, the first segment of four bytes from that section is:
5A 00
B1 04
Which if you assemble those tiles in that order (or
any order really) don't make a recognizable map tile. In fact there isn't even a tile B1. I'm so confused...