Good to know that there're over 100 blocks left. There's no absolute need that one single tilemap covers every room. Each room might get its own tilemap with 256 blocks. That would just eat up more memory, but the rooms could be loaded from disk or cartridge, so I don't want to restrict the graphics here. My converter actually works this way, it reads the PNG of the mockup and builds a tilemap and the tiles.

Yeah, mine too. Btw, there were some minor pixels wrong, fixing those I got it down to 141 chars.
But in any case, I think loading a charset and a screen (+color RAM) for each room is a bit prohibitive, especially if the screens are not made up of bigger "meta blocks". I think using two or maybe three charsets and keeping them in memory might be more practical.

I had a few minutes, so I made a quick POC to show that the limitations work. A few pixels had to be fixed, e.g. the hires tiles in the background are not possible that way, because they're against black (or brown), which are not available in those chars. Also the two black corner pixels at the bottom of the purple block had to be filled in, as there's no black in those chars (foreground color is purple). It's hardly noticeable though.
Check it out: http://galway.c64.org/~sid/pharao.zip

Screenshot, for the emulator-starved:

Apparently it's not ok to just say nice things here about the art if it's less than 2 lines of text...
Way to go, making sure the coders just stay lurkers here!

So I'll just add that I don't just like the visuals here a lot, but that I also think that from a programming point of view, I don't see a problem with the restrictions. I think this is totally doable.
I'm just wondering how the golem would look animated, i.e. how much his hands can move away from the body with the whole thing still looking nice.