Urg... Lots of noise, which seems a pretty NPA effect. It's cool but makes it seem like some sort of compressed scaled up image, like a JPEG. Oh, JPEGs...

Onto the actual spriting, the character's quite easy to read especially considering the low pixel count. I instantly recognized it as a tanned guy in a green shirt carrying a large gun and wearing a helmet. Correct me if I'm wrong at any aspect.
The portrait, on the other hand, I didn't quite know what it was at first. I knew it was supposed to be a face, it just didn't look like one. Same for the blue blobbish things. (What are those, anyway?) So I did a quick edit, starting first with recreating the image smallscale, which was the hardest part I have to say. I also made some tiny palette tweaks, rly tiny. Mostly reducing the number of colors by minuscule amounts and adding some things here and there to the image, hue shifting + a bit of antialiasing (not sure if you wanted that since it's quite noticable when zoomed in but also easy to get rid of). I also tried to... fix the banding in some places...



Now I know how hard it is to work with such a small level of pixels without giving up the things you're not supposed to do large scale. But it was worth a shot, no?

ALSO in black!



Just noticed, "DOOM" starts to read as "BOOK" at that size...

You're doing a bit better now. Bit of cleanup could be used on the ocean. The gradient could be a bit more circleish. And ptoing, I am digging that edit.

I don't really know what I did with your "Ninjas hate Pirates" piece but I kinda like it.



Observe. See how things are shaded and don't really have outlines? Well that's about all I can come up with for now, later I might have something more.

[snip]

I did some quick box dithering to get a feel for bringing down the harshness of some of the colors and contact points. I think this helps in some ways and hurts in others. It comes across more as dawn than dusk to me now so I may bring in more of the orange to bring back some of the vividness of the sky.

Honestly I have to say this one is somehow the easiest on my eyes and with a bit of smoothing up the dithering, perhaps adding some detail here and there, it'd be quite closer to finished. But the latest update almost seems somehow worse than what you started with. How do I explain: the two colors clash with eachother a great deal, and the level of detail and most of the dithering is so small you have to squint to see it. I think this is because it's being used on such a large scale, yet you're still using it as if the piece is smaller. So I see no use in it, really. All it does is make what's supposed to be the sea look more like some sort of very rough fabric or the static you see on old televisions, just blue-r. And I've never seen the sun glow so brightly, which is why I believe you should bring back the clouds and make the sky get darker gradually as it moves away from the sun, but more of a radial gradient.

Actually, come to think of it, at a size like this I'd listen to st0ven--unless you make use of the "pixel" aspect this would be much better off as a vector piece. But for the pixel aspect thing, I think you could do by scaling down the image a bit, in my mind (but that's just me).

One last thing; did you ever consider bringing up references? I think they'll help you greatly in determining how to properly shade and depict things and which direction you want to take it in, and how stylized you want to be. Here's one... And here's another but the first one was better.

I promised an edit, but I ended up doing this instead. Not so much an edit as it is a guide to help you, not sure if that's allowed here. But I suppose that as long as it helps somehow, it's useful, so here ya go.

Since there didn't seem to be a template around I made one up myself by cutting the pants off of that girlish sprite towards the lower left (I suppose it's from an anime or manga, but I don't know about very many) and the bald head from the one up top. I thought it looked decent enough. Then I tried to interpret what it might have looked like with a little more character and proper(ish) anatomy (rather basic, though) and this is the result. However I gave up turning it into a sprite because by the time I was done with this thing I was too lazy to go on



Left to right, template, interpretation, sketch I started the interpretation from.