I think before you decide to pixel more random things, you should decide what you need first, and then pixel according to it?
I don't necessarily agree with integrating something into the storyline or gameplay or such that the player themself sees, but the character doesn't. Not only is it bad for role playing, but it just doesn't make much sense, imo. The character wouldn't actually see it, so realistically, he wouldn't know. I'd just find it much more appealing if this something was visible or made known to him, rather than only to the player, even if the character doesn't at all interact with it.
But, that's just my opinion, I guess. If that doesn't make sense, let me know.
I also don't know how much sense it would make for a species to be existing and having a fossil of that same species buried under dozens of feet of hard rock. I imagine said species would have adapted or grown immune to whatever weakness they had that were killing them off before. But I am no paleontologist, let me tell you that...
Something organic is much needed in what seems to be a plain, dry, environment so far, another element, something that is alive would really make it seem alive. Just remember to use some interesting colors. Make those plants contrast the bare, lifeless ground tiles. (No offense intended.) And don't be afraid to go crazy with them, and experiment. If it's anything like I'm picturing it in my head, you could do something great, here.
Sorry if I sound harsh, I just might have a bias against these typical dry landscapes, a little something inside of me always dies when the next area in the game is a desert. (I'll always prefer the soothing green and blue of a tropical rainforest, for example.)
But all that aside, what you have so far looks bad by no means, technically well-made, and aesthetically pleasing too. I really like those dark underground rocks for some reason.
I also love that little red guys concept art, he looks like he'd go great with the tiles. Lots of character.
As for the tiling, outside areas should definitely have some visible ground underneath the actual floor, as for caves, I'd probably say none. Not much of a reason really, but with the outside tiles, it brings interest, I think, instead of having a large black area across the screen. With caves, it'll give the player more of an enclosed feeling, and provides nice contrast with the outside tiling method, open-endedness should you choose to go that route.