OK, first of all, you need more contrast. Lighter shades, darker shades, colors varying more in hue. The high contrast dithering, however, looks a bit distracting. Replacing it with a banding effect will make it look more tranquil.
The characters' feet are very small. I think you should give them bigger feet or change their shape so they'll seem a bit more sturdy. At the moment, they look as if a gust of wind could topple them. They'd also be able to take longer steps, so you could slow down the walk animation a bit.
Brighten the outlines a bit around the brightest parts.
The characters can share the same highlight color without looking very different.
I enlarged what I assumed are gems. You have a lot more space in those 16 x 16 pixel tiles, so if you use more of it, you can add more details to make them easier to read.
Here's an edit where I've tried to change some of the things I mentioned. It uses the same amount of colors as yours.
Hope that'll give you some ideas.
