I wanted to try something with 4 colors, but I ended up only using 3.
I went with different shades of the same color, basically, and this is what I came up with:
(regular top-left, 2x zoom on bottom)


It's supposed to look as though there is ground right in front (bottom)
with lava illuminating the rocky bits, and then a sea of lava behind that,
and then a dark, mountainous area with flames (spewing smoke).

Now clearly if I have to describe the piece, I've screwed up royally.
What I'd like to know, is what I could do to make this piece look better.
So constructive C&C, everyone!

PS: I realize this concept has probably been done to death. My apologies in advance.

Oh wow, that's almost exactly what I originally had in mind! 
Yours has more believable depth, the dithering is less linear,
and the lava looks more like... Well... Lava.
I like it!
Anyone else have an opinion or perhaps a different take on it?