Now the head of Boss merges with floor and it is not clear - how high this head relative to the floor. I tried to add a shadow:



But it's not solve the problem and complicated perception of the image, saturated with many details.
Any ideas to solve this problem?

Also, color of this character doesn't fit well with the level:



I tried a few variants:



And they are all terrible   
Anyway, which of the four do you like more?

If a anybody have good idea for colors of this character, please tell me. Or make edit! 

Here is character and level:




PS: Sorry for my bad english 

It's even full of duplicate tiles, so plenty of room for expansion.

You're right. But then I need a good solution to arrange this tiles so that it will comfortable in level design. In this case current tileset is very good. Btw, a small change (that white block near computer):



to make laser beam started from the grid:

I don't imagine you'll be anywhere near the limit for sprites. Unlike background tiles, NES can flip sprite tiles horizontally and vertically. So if you've got a left facing tank in the set, you also have a right facing tank for free. 

Haha, that's cool, so here it is:



I make a small revision, following your advice about sprites. Also, now items on the map and in the HUD are same.

Still WIP, now I have to make color conversion for bugs and doors.

 

Actually, you don't have more than 256.

I have 216 (12x19) now:



+version without black

This tank on bottom of tileset can turn his turret (NS and WE), but I'm not sure how is easy/hard to realize it for NES game, so removed all turrets rotations.

I checked the lazy man's way which ignores possible same tiles that share a palette.

Maybe I should use 8x8 grid (now is 16x16, except gui stuff) for this tileset, it would greatly reduce amount of (same) tiles.

If the HUD pushes it over, you might want to make it not occupy the same lines as the main level. (Right now it's on the same row as what looks like a door from the main map.) There's a way to swap to another set of 256 tiles mid screen, (Kirby's Adventure does it), but it would affect everything on the row.

You mean this row?



Well, apparently I'll have to find another solution for HUD/south door, ok.

---

Trying test this tileset in Tiled Map Editor. If somebody have this program, you can try to build your map, here the source, just place tileset in same folder with map.

Now with 4 color sets:


+objects\enemies:


all sets step by step:


current version\previous version (12 sets):

Thank you for answer!

The HUD also breaks lots and lots of rules assuming you haven't intended to use sprites there. Like I said in an earlier post, I recommend you post the actual palettes you've chosen with the image so it's easier for everyone to check this stuff. Here are my guesses as to your intended background palettes:

So, here is the actual palettes for tiles:



(Through this I found a new errors with colors)

...And actual palettes for HUD:



Now I reworked it - fixed some colors and alighned all 3 color's elements with grid.

But sprite overlays should be used VERY sparingly, because of the eight sprite per scanline limitation.

Allright, now only 3 colors on the character/game object, not a great loss 



And question due to this - can I use different 3 color palettes for various animations/frames of one object? Like this tank on the bottom row of last picture. When tank makes a shot, it used the other colors.

---

And as the sum of all stuff: