You shouldn't use pure black outlines, since they waste the little space you have.
In fact, why use 16x16? It's too hard to convey texture in such a small size, you know?
I'll leave you with this image (by the always skillful
Arne), and the advice that you should use a bigger canvas size for the little guy