The speed of sound in a gas depends not only on the density, but on the pressure. In fact it depepnds on the ratio of pressure to density, it goes up with increasing pressure, and down with increasing density.
http://hypertextbook.com/physics/waves/sound/
There are several forms of the equation for the speed of sound, the one I'm referring to is:
c = sqrt(gamma * pressure / density)
here gamma is a thermodynamic property of the gas, the adiabatic constant. The pressure and density speak for themselves.
The above equation can also be found in Goldstein, "Classical Mechanics".
For an ideal gas, the ratio of pressure / density depends only on temperature and the molecular weight of the gas.
So on earth, the speed of sound varies with altititude, but this is almost entirely because temperature varies with altitude.
More on the formula for the speed of sound in an ideal gas can be found at:
http://hyperphysics.phy-astr.gsu.edu/hbase/sound/souspe3.html#c1
The most fundamental formula for the speed of sound in a uniform medium is that it is proportional to the square root of the medium's elasitc property, the bulk modulus, divided by its density.
c=sqrt(B/rho)
If you consider the media to be a distributed spring-mass system, the bulk modulus represents the "spring" part of the anology, and the density represents the "mass" part of the anology. It makes a intiutive sense that making the springs stiffer increases the speed of sound, and that making the mass heavier decreases the speed of sound.