Sorry, guys, but you're misremembering. The speed of sound is *not* strongly related to the density or pressure of the gas. It is strongly dependent on the temperature.
For an ideal gas, the speed of sound c = sqrt(g*k*T/m)
Where:
g (actually gamma) is the adiabatic index - the ratio of specific heats of the gas.
k is the Boltzmann constant
T is the absolute temperature
m is the mass of a single molecule of the gas
Now, most gases are not quite ideal, but air is quite nearly so, and the effects of it being non-ideal are small. The speed of sound changes with altitude because the temperature changes with altitude.