Hi Nirel, thanks so much for doing some examples, great variation.
Really hits home the importance of readability (as mentioned further up)!
Based on your examples, the advice above and a couple of other cases of trial and error, I ended up with something like this (still hovering around a sunny day / early evening approach), will probably fade the tiles out a little more on the next pass:
I basically ended up making the characters more of a vibrant colour, also changed the temperature and texture of the foreground tiles a bit.
Not sure if it works fully, but it works better at least.
Cheers guys