I think dithering is a bit out of vogue these days. It's a lot of work for little reward, and your art would be much cleaner and more readable without it. Maybe try anti-aliasing instead -- that's where you take a middle color and soften the line edges between two colors. Your dirt colors could use some adjusting, as there's a really big leap between the two middle ones.

More colors isn't really a problem, at least, not these days. But having fewer colors makes managing them simpler, and produces cleaner art. Plus, well... with fewer colors (or a smaller canvas) there's really only so much you can do wrong. If you keep pushing the pixels around, they'll eventually fall into the right place! (That's how it feels to me, anyway, haha.) It's hard to effectively pick colors in a program like Paint -- maybe try GraphicsGale (it's free.) It's similar, but with layers and color management.

You don't need to scale up your work, by the way! You can click an image to zoom in. :3