I think ft has got the explanation exactly right on this.
Chorned, I think you are confusing adiabatic lapse rate with the adiabatic compression involved with the propagation of sound waves.
Newton did not know about the gamma factor, you are right on that though.
Humidity (i.e. gaseous H20) has only a negligible effect on the speed of sound, up to about 0.6%.
Another good formula for speed of sound in knots is 38.94*sqrt(T) where T is absolute temp.