These things will actually be rather large
A true Self Replicating Machine would probably mass out to 100 tons or so--an HLLV payload
http://www.rfreitas.com/Astro/TerraformSRS1983.htm
The problem with very small things is that you swap ruggedness for complexity.
radiodurans is tough:
http://www.genomenewsnetwork.org/articles/07_02/deinococcus.shtml
--but it doesn't do much.
Waterbears get by because they are small.
But a newly fertilized egg cell can--in about 20 years--become an aerospace engineer student.
But put that egg cell in the dirt--and it dies, while the other two live.
Brownian motion shells you at small scales. Static cling holds you fast like neutron star gravity--or flings you away from a desired target. A droplet of water is an ocean of molasses. Propellaers won't work--maybe a whiplike tail from a sperm cell.
A dust mite is godzilla, a dust mote is an asteroid--and heat is death.
I think people like the idea of nano pixie dust in that you wouldn't need large rockets to build a moonbase. Just shoot some utility fog at the moon and let it build things for you.
I don't think that is ever coming. Want a moon base? Launch a front end loader with an atomic pile atop Sea Dragon.
https://en.wikipedia.org/wiki/Sea_Dragon_(rocket)