Hey HAZman, looks like you're off to a great start.

I'd like to correct your terminology a bit if I may: the checkerboard pattern you're doing is called dithering, not shading. Dithering is pixel-art-specific technique primarily used to smooth the transition between shades, or to create new shades altogether (though that's really two definitions of the same thing). Shading, on the other hand, is capturing the volumes and shapes of your subject based on how it's receiving light, and it's used in almost all forms of visual art.

I don't mean to be pedantic, and I'm really sorry if I sound condescending, but it's important to keep in mind that dither is optional, shading is not. If you have your shading right, most pieces will work with or without dither.

DeadHorse.flog();

Anyway! I'd suggest removing as many of the internal black lines as you can--define your forms with shading instead. And it's never too late to antialias. Go for it. In fact, it's usally one of the last things you should do anyway.

Also, it's usually considered more visually interesting to shift in hue as well as lightness along your color gradients. For example, your tan midtone might shift into reds/purples as it moves into shadow. I know it doesn't sound like it makes much sense, but play with it for a bit and you'll see what I mean. Shadows tend to be more blue, highlights tend to be more yellow.

Please let me know if any of this is unclear, I have a bad habit of being a bit jargon-y. Welcome to PixelJoint.

Here's an update using the advice I received on shading.  I need to work on the colors a bit, but otherwise I'm liking how it's looking.  I've also done a bit of anti-aliasing, mainly on the right half of the image.