The space between molecules isn't the way to go. Crystal packing distance or 'space between molecules' works two ways, actually, in determining the speed of sound because the speed of sound depends on the bulk modulus and the density.
Solids and liquids do tend to have increased bulk modulus over gases. They are harder to compress. So more dense things tend to be more incompressible, generally, though not always, and the difference in compressibility among transition metals of widely varying density is really complicated. Rubber is more compressible than concrete of equal density. The speed of sound depends on the bulk modulus and the density to decrease it. Why these things?
The speed of sound increases by the square root of the bulk modulus and decreases by the square root of the density. If you really want to understand more clearly try to picture the translation of the wave through a rarefaction and condensation both in terms of the work done and the change in momentum of a point volume. The work stored in a displacement for a point volume to translate through a distance, or wavelength, depends on elastic properties of the solid or fluid (bulk modulus, the ratio of volume stress to volume strain) which directly ties to energy (the area under the stress-strain curve), or you can apply the pressure times a change in volume thinking of thermodynamics if you know vector calculus. This is the material properties version of Hooke's Law, or F=-kx, for a mass spring, and it's super important for orthopedics by the way. The higher the bulk modulus the shorter the compression the less forceXdistance or work is required. Think about it this way. Imagine a long frictionless plane. On your left you have stretching off in a line towards the horizon resting on the plane a line of solid spheres connected by very loose springs, one between each sphere, at equilibrium. On your right you have stretching off a line of the same spheres, but between each sphere is a stiffer, stronger spring, with a much higher spring constant. If you started oscillating the one nearest you on the left and the right at the same time at the same frequency longitudinal waves would propagate along both lines, but they would go much faster on the right because only a small particle displacement would store enough energy to send the wave on. The speed of sound increases with the square root of the bulk modulus of the medium.
Now imagine if both sets of springs on our frictional plane had the same loose springs, the same spring constant, or similar compressibility if you want to think about it like material science would. But now, imagine, instead on the left the spheres were of cork and and on the right they were of lead. Instinctively I think of time, so thoughts leave work & energy for a moment and apply the thinking of dynamics, which involves the relationship of change in momentum to force and time, or impulse. The more inertia within the medium the slower the wave. The speed of sound decreases with the square root of the density.
So a medium which has a high bulk modulus will send the wave on quickly because there isn't much displacement needed to store the energy of the wave.
(((Bulk modulus is the relationship of volume stress and strain, like sheer modulus is for sheer stress and strain, and Young's modulus is for tensile stress and strain, which is all there is to elastic properties (except breaking point and basic hysteresis) for the MCAT)))
A medium with a high density sends the wave on more slowly because of the inertia of the point masses.
Working through this reasoning you still need to understand sound in terms of what is the decibel scale, what are beats, and what are standing waves in air columns. To reprise the main idea here, the speed of sound in water would be much faster than air if bulk modulus were all there were to it, and speed of sound in water would be much slower than air because of its density. It all works out, though some liquids are faster or slower than this, some gasses or solids, that the speed of sound in water is 4.3 times faster than in air.
That is actually the type of thinking I was trying to get into. So let me know if I'm understanding this correctly. When you are referring to the frequency of a sound wave, you are talking about the amount of cycles a molecule will go through as it is disturbed and returned to its average position. When a sound wave reaches an interface, such as air -> solid, the air molecules will be colliding with the solid at the same rate that the air molecules were colliding with each other to propagate the wave, so the molecules in the solid will now have to be disturbed and returned to their average position at the same rate. But now you have molecules within the solid packed more closely, so the disturbance will travel faster throughout the medium, and as a result the wavelength must increase.
Edit: It also kind of helps to me think in terms of compressions and rarefactions. A longer wavelength for a sound wave would mean a longer region of a rarefaction/compression area, which you see as the wave moves through a solid. I'm kind of drawing it out in my head, where you have a region of compression for air (shorter) moving to a region of compression for a solid (longer), resulting in a faster wave propagation. Again, since these molecules are colliding with each other at the interface, they must be disturbed and returned back to their average position at the same rate.
Let me know if there are any holes in my reasoning.