Dithering is used when you want a color you do not have, so you combine the two. It can also add texture. It doesn't always have to be strictly checkerboard either, it can be looser.
Your rocks have confusing shading, maybe try more geometric blocks? You can get a lot out of a single flat shade for a flat surface. Especially on rocks.
I wouldn't really call what you have inherently flat, I'd just say that the depth isn't working as well as it could so it leads people to assume. You have many more values than cavestory or whatever.
Here's something Opacus did last year that your stuff reminded me of.
You can look at how he did his rocks to get an idea of how you could shade yours.
Here's something rendered in 3d which could also help you out:
Mainly with the forms
And of course, nothing beats the real thing so you can also look for stuff like cliff faces and rocks to get an idea of how you might want to represent them in your game for a more convincing look.
Welcome to pixel art, by the way. C:
And haha shrike posted while was looking for images.
