Physically, his skin was grey, as were his glasses, hat, clothes, and long coat. The Grey Man's hair was silver. He was an energy network that when killed, his dead body would break down and his energy would recreate a new body. If attacked with enough force, he could be "permanently" killed. He had power equivalent to the Eye of Harmony, which allowed him to pluck a TARDIS from the time streams and transition between the physical plane, Cathedral, and interstitial time.
In the distant past, the Grey Man's people imposed the concept of duality ("good" versus "evil", "us" versus "them") on the first humanoids to evolve, which resulted in the beings destroying themselves in bacteriological warfare. In opposition to this the Grey Man used his soul to build Cathedral as a metacultural engine that would introduce uncertainty into the universe. His people considered this blasphemy and exiled him. But since he used his own energy to create Cathedral, as long as it existed so did he. Despite being the creator, Cathedral and its people were ruled by the Mandelbrot Set, a set of stone heads that ruled from the Cruakh.
In 1994, the Grey Man drew the Seventh Doctor to Earth after he became aware of the threat of Gabriel and Tanith. He was killed by them and later by Jane Page, after which he pulled Bernice Summerfield's soul to Cathedral to keep her safe.
The Mandelbrot Set wanted Gabriel and Tanith destroyed since they generated entropy, and the Grey Man took them on directly. They were able to kill him, and his energy dissipated, with his death being felt by people around the world.
When Gabriel and Tanith attacked Cathedral and destroyed it, the Grey Man reappeared and stated that he had cut off their power. No longer immortal, Ace killed them both. As Cathedral's plane disintegrated, it continued its existence with the Grey Man's form and identity. (PROSE: Falls the Shadow)