Little update!

Had a try on fixing the characters perspective. Feels like made new dudes and still didn't get it right.
Girl looks kinda weird too and both look like kids. 
Played some games like Zelda and Bombermans (SNES ones) to have some ideas. Surprisingly, they had the same kind of perspective issues on the characters and scenery, but i guess it feels like it doesn't clash due to the giant head the characters had(?).
Well, if all else fails, i'll keep it like in the first mockup. It can't be that bad! 
I think the reason they look like kids is the size of the head. You could make their body slightly larger - I'm very bad with proportions so I can't tell you how large exactly - or their faces smaller, but that would cost you the eyes.
But given the plastic-ness of the other game elements (like the walls and the ground), is that really a bad thing? They fit well together.
You could however try and give your stones and ground more structure, and see if that changes things for you.
For the "ceiling", you could try and recapture the structure of the wall, i.e. the ceiling could be the stones from above. In this case I would chose the 4 row variant, show the outer stones from above (in a darker shade) and then have any remaining space black.
Also in your last edit, the stones have different borders depending on whether they are aligned with the tile or not. I recommend taking the small borders (1 px) for a more "mature" and "realistic" look and 2 px for a more "plastic" and "toy-ish" look, because it makes the stones look more chubby.
For the natural walls, I'm thinking about that myself a lot, and I think one important thing is to keep the base line uneven. This is what I did:

Look at the "cliffs", they are not one straight line, but they keep going in and out. The implementation might not be perfect, but I think the idea is good.
Also, natural walls tend to crumble etc, so you might want to have some rubble lying around near to the natural walls.
But it all depends on whether you want to go for the "toy-ish" look or for the "realistic" look. The important thing is that you keep it consistent, then you can make anything look good.