That's just it. Even with large pressure changes, the speed of sound is virtually unchanged. At about 18000 feet, there is about half the atmospheric pressure. But, whether an airplane is flying at sea level or 18000 feet or 50000 feet, Mach 1 is still the same for the same temperature.
So, the distance between molecules doesn't seem to be a factor. That's one of the paradoxes of it and, one of the things that seems so intrisically sensible that it's widely accepted that air pressure simply must an effect on the speed of sound propagation.
Your musings about it have been very helpful in sorting out some of the things that seem to be happening. Even when I may not agree with it, disagreeing makes me have to think about it in new ways.
Firstly I'm glad to have helped. I woke up this morning and had a bit of a think over why the pressure may not be a factor. If sound is created by a force, this this force has to be spread over a greater number of particles meaning a lower average force felt by each particle. (i.e. air of greater density). Alternatively in airs of lower pressure the force is shared by fewer particles which means each particle would experiences a greater force.
If you think in terms of doubling the pressure. The particles have to travel half the distance before transmitting the energy, however the force has to be spread out over double the amount of particles. This would effectively cancel, as the lower speed is accounted for by shorter distances and vice versa, hows that tickle your fancy?