save as a png-8 should keep the size small and keep the high quality.
PS. I loaded the above image in CS3 and noticed the pixelization your talking about. Does it look like this when you open the original image?
Some things you might want to check.
1) image>mode whats the bit/channel set too?
2) image>pixel aspect ratio you might want to try resetting to the default settings. Maybe you accidentally messed it up.