Red rust is ferric oxide. That is active rust eating at the metal. Black rust is ferrous oxide. This is when the rust becomes inert. (passivated). It is no longer active, and actually will protect the metal beneath it. So called "conversion coatings" are designed to make this happen, rendering the surface neutral and ready for painting. Conversion coatings for steel usually contain nitric acid. For aluminum, its phosphoric and chromic acid. In heavy deposits, ferrous oxide is also brittle, so when it cracks, it lets in new moisture and oxygen which start the rusting process anew. Acid based rust removers, as well as Evaporust, may leave deposits of ferrous oxide, especially in pits, that may require some mechanical agitation to remove.
A black residue on the surface is passivated light rust, and easily removed. The dull gray is the result of the rust and acid etching the surface so that it doesn't reflect light. It is the actual color of the metal.
Another method of rust removal is sodium hydroxide (quick lime, Draino crystals, etc). It is a strong alkali, and will remove organic paint coatings as well as the rust (doesn't work on epoxies and two-component polyurethanes). Down sides are it is extremely toxic, can easily permanently blind you if it gets into the eyes, and will burn your skin. It is what was used in slaughter houses to dissolve all unwanted parts of the animal. If you pour it out in the yard, nothing will grow there for a period of up to years. and you will have a black soupy mess as it dissolves anything organic in the soil. It eats aluminum, and will cause a violent reaction to it when in strong solutions. (Having witnessed this, its akin to pouring water into a pot of boiling oil)
A chemist could better explain the valence of the molecules and the reaction that leads to their forming.