The floor looks less like television static, so that's a start. When you have black outlines on your character, it's wise to minimize the amount of black on the walking surface. But now I've no idea what the floor should be. The chinese one used dots and lines of grey sporadically, it makes it look like weathered, old stone. Also, I see now that the water and floor share the same palette at the expense of the shadows on the water (replaced with black dithers). I would definitely not go with that purple and cyan water though. Looks like ectoplasm or something. I would change the white in the palette to "32" and leave the grey as is. The NES palette doesn't have a subtle enough range of colors to push things like that.
Well, in the original Final Fantasy VII the water is purple.
Also, I like the purple on cyan. I am aware it looks weird, but that was what I was going for. The color combination sets "another world" environment and has a mystifying mood to it, kind of like death itself. Hence, the purple relates very well to the environment.
I have this feeling you don't like the stairs. Here's an edit

Notice how it looks like "weathered, old stone" now.
I was conservative on editing the stone since I was doing mockups and don't have the patch Lugia2009 has. I just removed the black in MS paint. I have edited a map before for this hack as a demonstration for Lugia2009. It's A LOT of work so please keep that in mind. Lugia right now I believe is map editing with a hex editor so it is easy to get very lost in the process.
and it looks like he's walking with one foot in front of the other, like a model on a catwalk.
Do you play a lot of NES games? The NES is restricted to a certain amount of graphics so many do that... A LOT and results in many games having choppy walking animations
In this NES game, it is even more restricted. This game restricts you to display a lot less than a standard game would allow (I could explain but I don't feel like it). The original game had the "catwalk" walking so the hack will have catwalk walking as well.
Also Lugia2009, it would help a lot posting by posting the latest patch so I can do so a lot more constructive edits instead of doing mediocre edits on MS paint.

I don't like this edit. Cloud looks like some 10 year old kid. (And why does Cloud have BLUSH!?!). The style isn't even right for this game. The head placement looks really awkward and makes it look like cloud has no neck And he looks like he's on a catwalk, ironically.
My version: