If you think of the time needed for one molecule to travel to the neighbouring molecule and then to transfer its momentum (crude mechanical idea but sufficient for this purpose). This tells you the speed at which the 'influence' of vibrations can pass through the air will increase as the molecules travel faster. If the gas density increases then a molecule will meet another molecule in a shorter time but that molecule will need to travel again before it meets a third molecule. The time for the actual 'influence' to travel over a certain distance will, thus, only depend upon the average speed of molecules and not how close they are together.
Furthermore, for solids, the speed of sound depends upon the stiffness (modulus) and the density. Faster for stiffer, slower for more dense. For two substances with the same stiffness, the more dense one will transmit sound slower. If this is counter-intuitive, it's because our experience is that more dense materials are usually / often more stiff.