Water loses kinetic energy when it detaches from the surface of the ice
Water molecule in the solid phase have more hydrogen bonds than in the liquid phase. It takes energy to break these bonds, so only molecules with sufficient kinetic energy will detach (maybe because they just collided with a water molecule that transferred some kinetic energy to it). So the molecule that detaches will have a low kinetic energy as it goes into the liquid phase. Further collisions will quickly ensure that over time, this particular molecule has an average kinetic energy, but overall the temperature will drop from that detaching event.
Water gains kinetic energy when it attaches to the surface of the ice
This is just the opposite process, so the opposite happens. As additional hydrogen bonds are formed, the molecule has greater kinetic energy (in the form of vibrational energy). Either the molecule had less than average kinetic energy and now has average energy again, or it had average kinetic energy and will have higher kinetic energy, but quickly dissipate this to other molecules.
When you add salt to the liquid water, less molecules attach to the surface of the ice
Compared to pure water, less collisions of particles in the solution with the surface of the ice will lead to attachment of particles because now, some of these particles are not water molecules but sodium or chloride ions instead (they are not incorporated into the crystal lattice of ice but stay solvated by liquid water). As a consequence, there are less attachment events while the detachment events stay the same. With a net melting of ice, the average kinetic energy of particles decreases (the temperature drops). As a secondary effect, this also affects the rates of attachment and detachment, so once the temperature has sufficiently dropped, the two rates will be the same again.
What energies (kinetic/temperature vs. latent/chemical) are involved, and where?
In my explanation, I talked about kinetic energy (reflecting the temperature) and energy necessary to break hydrogen bonds (could be generalized as intermolecular interactions, and they underlie the observed bulk latent heat).
How exactly (atomically or subatomically) is one type of energy converted into the other
There is no chemistry or nuclear physics happening, so it is sufficient to talk about the molecular level. Kinetic energy is converted into potential energy through inelastic collisions. Kinetic energy is redistributed between molecules through elastic collisions.
Why is each step energetically favourable? Or is it not, and it's reversible? How reversible, statistically?
According to microscopic reversibility, all molecular events are reversible. Processes go in a certain direction because it is more probable than in the other direction (2nd law of thermodynamics). The 2nd law of thermodynamics is inherently linked to large numbers of particles, so you need to look at the forest rather than at individual trees.
How does the concentration of salt change the evolution of the system (again, at a microscopic level).
The higher the concentration of the salt, the lower the concentration of the water in the liquid phase, i.e the fewer events of liquid water attaching to the ice.
How does adding e.g. ethanol instead of salt change things?
1 mmol/L NaCl has twice the dissolved particles compared to 1 mmol/L ethanol. Otherwise, the effect is the same (colligative property).
Is liquid water required at all? Is salt able to melt and cool completely frozen ice, or is external force required (stirring, driving over it, etc.) to cause some initial melting for anything to happen? (I've read conflicting answers to this in the past.)
Ice near the freezing point exhibit surface melting. Once there is a tiny amount of water, more ice will melt. On the other hand, if it is cold enough that even saturated solutions will freeze, a mixture of dry salt and ice will not interact.