Note that a tile is 8x8 big and a sprite is 8x16 big. So if you have, let's say a 16x32 sprite you can use up to 12 colors (only 3 colors per 8x16 block though).

Yeah, I'm unsure of how to fix a sharp-looking sword too.

As simple as this:

The dithering doesn't add anything in this case, it just gives the skin unwanted texture.

I'm in.

I prefer cool and atmospheric over cute and like original characters/creatures.

As for your latest sketch, the texture still doesn't feel quite right. It looks even more like wrinkled up paper now, or maybe tree bark. Again, I'd study the edit Surt did for you, as well as the reference photos that were posted. The textures that were posted for you have all been sharp, angular, and large/flat shapes. Everything you're posting is much bumpier/noisier/organic looking than it should be. Work with big, flat shapes, at first, then add a little texture later.

The sketch was more to get the tile layout I need. The structure is still very incomplete, it's just the basic structure, I didn't add any features yet.
Here is a little update on it:


Take a look at these pictures:
http://www.winsoftware.de/screenshots/big/grand-canyon02.jpg
http://www.geo-reisecommunity.de/bild/regular/352115/Grand-Canyon-North-Rim.jpg
Do you see the big vertical patterns on the straight faces? Those are kinda my reference. There is more to a cliff/canyon, but in tilesets you have to simplify and especially in 16x16 there isn't much place for multiple structural details.

About the flat & angular thingy: keep in mind that the structure of rock is quite depended on the forces working on them. In deserts you have quite strong winds which make the rocks more round. Maybe you should take a look at the reference image that were posted here yourself, the rocks you see there are almost all round.

Also, as a few people have already mentioned, your cliffs should be around the same color as your sand, since they're made of the same material. Just changing your cliff colors to the sand colors would probably help a *lot* with making them look more like cliffs instead of trees, if you want to try that first.

Don't you think I already tried that? It simply looks way too dull. By the way the highlights of the rocks have the same color as the sand, take a look at the previous cliff tiles, it's what makes it blend that nicely together at the top.