16-bit sprites used 16-bit color palettes. It doesn't necessarily have to be a certain size. Technically, a 16-bit sprite could have up to 256 colors at once. I'm not really sure how to make a sprite look more "16-bitish", though I certainly know what you're talking about. The first thing that comes to my mind is just adding more detail and shading, but I'm really not an artist so I'm not sure.