Now he looks Evil:



The gif has 11 colours while your had 8, I had to add 2 tones of red for the blinking eyes effect.

While looking at the palette I noticed you have 2 similar values #48283F and #442C3B one of then is only used for a stroke of the head as is shown in the image:



So my advice is leave room for extra colours for any effect you want to add later, but I suppose this is still wip and you already have thought about it.

Finally found this .sid :
http://hvsc.tp2.be/C64Music/MUSICIANS/A/Ashrilyn/Metroid_Brinstar_Remix.sid

Looks quite nice.

But if the fish is trying to jump, instead of looking stiff in the ground it should move it's tail.

wait. . . 235 colors?  what the heck is that?  and it's still .png?  what kind of image compression is THAT!?

I case you didn't mean it as sarcasm, the png standard defines indexed modes with a palette of 256 colours or less,yes, it doesn't make much sense to not use a palette with the size of a power of two, but it's still a png compliant image.

4.3.3 Indexing

If the number of distinct pixel values is 256 or less, and the RGB sample depths are not greater than 8, and the alpha channel is absent or exactly 8 bits deep or every pixel is either fully transparent or fully opaque, then an alternative representation called indexed-colour may be more efficient for encoding. Each pixel is replaced by an index into a palette. The palette is a list of entries each containing three 8-bit samples (red, green, blue). If an alpha channel is present, there is also a parallel table of 8-bit alpha samples.

http://www.w3.org/TR/PNG/#4Concepts.Indexing

I think it still doesn't look right, any ideas?