Try going even lower. Make your tiles in 8x8 first, then upscale to 16x16 (via nearest neighbor) and smooth out lines, add shading, whatever. Some tiles you'll have to redraw entirely. That will be tricky at first, but keep trying. Once you're comfortable working at that size, it should be easier to start directly in higher resolutions, but I'm not there yet.
Whatever you do, make sure to work with a restricted color palette like DB16, DB32, the Tango Icon color palette or even one of your own devising. Otherwise you'll be paralyzed by choice, and your tiles will look mismatched.