I love those clouds!
I would stay away from dithering as much as possible here. Texturing is fine, but with such a limited palette and small object sizes, I think it gets too noisy in this case. Single pixels don't really say much on their own. If you try to add texture with lots of single pixels, you'll end up with varying flavors of sandpaper. Sandpaper trees, sandpaper grass, etc. I think it'll be nice for rust, with the two darkest shades, and of course for the sand, where I suggest adding
more of that dithering to make it look more like sand. For other surfaces, I think you need more information than that single pixel. Putting a few together in a line will indicate cracks, a few in a tiny cluster makes a leaf, and so on. That way you should be able to add some interesting details without making it too noisy.
The thing I'd worry more about, however, is where you use your colors. By adding highlights and the dark shadows to everything, you lose depth. Everything seems to be on the same level, and nothing really stands out as more important than anything else. You've done well with the forest area where you have the faded, blue background elements, but I think the color usage in the ground tiles could use some adjustments.
I managed to misinterpret your sand as grass, but oh well.
It makes for one more texture example, I guess.
For instance, you can cut down on the use of black lines to separate brighter areas. If another, brighter color serves just as well, there's no need for such dark lines. I would save the use of bright and dark colors together for things that are really important, like the player, enemies or power-ups. I also removed highlights from tiny things like the smallest bricks to make it look a little cleaner and most of the highlights on the darkest ground tiles as well, since I thought they were attracting more attention than their purpose is worth.
I also decided not to mirror any tiles since I think it's well worth the extra effort. It's easier in some ways since you don't have to worry about the direction of the lighting being inconsistent.
Here's some sand too. I recommend adding some kind of sign of danger to the sand tiles, like some skeletons or skulls or something. It's not easy making them read well at that size, but I don't think much is needed.
I hope that's useful.
