Thanks 32 and yrizoud. I agree in all accounts. In fact I was doing a little reasearch and turns out the GBA and DS Mario&Luigi rpg series actually do the brightness shift trick, but much more subtly and only on the top (floor) surfaces, exactly like 32 suggested. Take a look here:

So, to get a feel of what I am planning to do, I color reduced it to have about 7 shades color ramps, recolored to my palette, and squashed it to 2:1 ratio 16x8 tiles, so I suppose I'll be looking to a similar density to this edit when I am done:

The brightness shift will be more a measure of contrast between the top and the front of the solids then, point taken. It is interesting as the mario game uses only three thresholds of brightness, leaving the darkest one for walls which work as backgrounds.
Also yrizoud is right about the texture, I went for quick mockup and pretty much made whole scene with only two tiles. For the surfaces I believe it will be best to use two tricks: 1-use more horizontal textures for the ground and more vertical ones for the walls; 2- what yrizoud said, use flat colors or subtle textures where a flat color is predominant and darker shades only show cracks, gaps, etchings, tufts of grass etc, more like what zelda does. However, I suck at subtle textures, I never seem to know what to show and what to hide, and the elements I place spaced away in the flat surfaces either don't tile well or seem disconnected from each other. I'll look for more references on those.