Half and half shading works, but there's a lot of other things you could do, such as dithering, or traditional shading (one source of light, and highlights and shadows).
Regarding colors, I think more contrast would look good. Your gun on that more detailed sprite looks great, and kind of pops. You may want to try giving the entire sprite that pop with some color or lighter shades. From experience, contrast looks really weird when you first use it, but it can make some great sprites.
To find palettes, just look up "pixel art palettes," and there should be a bunch to look from (I personally use the NES palette).
Good luck!
Would you try to do a source of light when working with 16x16 or would you only really do that till you get to 64x64?
I will try working with the NES pallet and see how it comes out, I always found working with a limit of colours really difficult.