Going with his surface area of 500,000 sq. kilometers, we would only need about 100 sq. kilometers of mirrors, spread randomly through the area to be emphasized, to produce a readable message on Earth. This is actually doable, although hard, and the message would only be visible at one particular angle (say, full moon directly overhead edit: depending on how much of the Earth you cover and how well, it may not need to be directly overhead), unless you want articulated mirrors.
In fact, I read, long ago, an article about a guy that performed this hack on Earth during the fairly early days of satellite photography. He drove around the desert in Southeast US, and placed small reflectors at angles calculated to reflect sunlight into a passing satellite. This resulted in huge overexposed letters in the satellite image, since each reflector exposed a very large pixel/grain of the fairly low-resolution satellite. I can't seem to find this article anywhere, although I remember it pretty clearly. If you can find it, I promise to upvote your submission!
I might help spending time choosing an area where you can avoid deep craters and have enough dust to form the piles.
Build a rocket ship that makes a flyby of the moon, drops some mirrors and returns. Maybe it could rendezvous with the ISS to get a fresh supply of mirrors and we send the mirrors to the ISS by conventional means.
And when I say mirrors, I am thinking of really thin ones. Really, just giant sheets of aluminium foil. I suspect they'll naturally drift around and degrade over time, giving people something to think about as a poignant metaphor of some artistry thing.
Rather than smoothing the surface to reduce shadows, Why not write in a color other than black? I'm thinking a laser in Green would work well and would contrast against black and white quite well.
More authoritative, and fun http://what-if.xkcd.com/13/
As a side note: I wasn't aware how _little_ surface damage nuclear weapons actually inflict. I was always under the impression that a nuke would level entire cities + surrounding suburbs.
You would need an array of mirrors about the size of France in orbit about the earth. Thin film mirrors would be a lot lighter than asphalt. Precisely aiming the mirrors would be the challenge.
or possibly
☮
Imagine you did this on Earth and how much you could save over nuclear bombing the place with paint. In fact, we already did it, as a side effect.