Not much pixelling, just a bit of experimenting:

Interesting decision to select blue as background color, because I think most NES games seem to use black and use tiles with another palette for the sky. But then the borders need to be square and cannot be round like in your case. (which is appealing)
Both the light blue and black are common to all background palettes so far, so either could be the common colour. If it's black then many tile could still be used without the sky, just need to replace the fringe tiles that contain some sky area.
And at least the metal platforms look very fragile with sky as background, maybe you want to add a 2nd layer of metal structure behind.
Yep I'll probably do this selectively. Do want to make sure what the floor line doesn't become ambiguous though.
Since they are so shiny and reflective (that's how I see them), they should reflect stuff though, at least crates and walls (have fun working that into the game mechanics).
Lazycow makes me wonder: is the bg the sky or a wall? I saw this as an interior scene, but then I think it would need cast shadows on that wall.
The lack of subtle colour differences and tile cound limits probably make such reflections rather impractile for the NES. Maybe darken them?
Is supposed to be sky, except the dark grey area which is wall.
I like the cliff walls better on the full sideview, the other ones are just a little too blocky, they look man made. I think if you just slanted one edge of any of those boxes it would look a lot more organic.
The side-on stuff is an abandoned earlier iteration. Just kept it around as there are still a few element in there I want to keep. I prefer the blocky cliffs to the blobby ones, but I'll try to work in a few more angles.
The trunks on the palm trees look like legos, still not sure if that's good or bad, but it doesn't look quite right just under the leaves. That part's usually thicker than the trunk since it's where the dead leaves pile up until they fall off.
Trying to minimise the tile count and work within the attribute table boundaries. I can't see how to make the bulge of the old leaf bases any wider without adding another tile each side or offsetting the whole tree half a tile.
I hope by putting this here too that means you'll be working on it more. You start so many awesome tilesets and never take them anywhere.
So long as my motivation holds out. Kind of builds on stuff worked out on previous ones.