NOTE: THIS WAS EDITED TO ADD INTUITION(ESPECIALLY IN THE END OF THE ANSWER)
The speed of sound is proportional to the bulk modulus and inversely proportional to the density of the material. In most cases(or all, please correct me if somebody knows for sure), the bulk modulus in solids is much bigger when the solid has higher density. So, while the higher density tends to give you a smaller speed, the much larger bulk modulus gives a larger speed.
Or to rephrase, the difference in density is much lower in the difference in the bulk modulus for two materials, so the speed of sound gets bigger from the less dense to the more dense material. So, the compressibility factor wins over the density factor, and thus "ruling" over the final answer.
"I have read that it takes more energy for sound to travel in dense materials so it takes longer but then neighboring molecules are closer so sound does not have to travel that far, making it faster. This doesn't make any sense because it says the more dense a medium is, sound is both faster and slower."
The power(the rate at which energy travels dE/dt) is given by the relation P=0.5*ρ*(ω)^2*(ξ)^2*Α*u
ω=angular frequency and its equal to 2πf
A=cross section area of material in which wave travels through
u=the speed of propagation
Now, say we produce a sound of a given energy in air(and thus constant power if we don't include loss of energy in our analysis). When the sound reaches the solid material, then it starts to propagate within the solid(and not the air). Now, for a less dense material(we consider the same bulk modulus between the two materials so as to just see the effects that the density has on the speed of propagation), in a given volume you will have less mass than the denser material for the same volume. So, in order for the power to remain constant, for more mass per unit volume(which is the density) and the same bulk modulus we must get a lower speed(check the relation that I wrote above about the power).
Density: The higher the density, the more mass you have in a given volume that tries to oscillate. But that also means that we have more inertial forces, so the material "resists" more, so the harder it is to accelerate the molecules in the volume.
Bulk modulus: The bigger it is, the solid is not easily compressed. So, this means that when a force of given magnitude gets applied to that volume, the volume will not be easily compressed and so it will be accelerated more pushing the volume of the material that is next to it. For low bulk modulus, it is easily compressed and thus for that same force it will be compressed more and so move less, pushing the volume of the material next to it less. So, the bigger the bulk modulus, the more a volume pushes(or pulls) the volume next to it, thus giving us a wave of propagation that is bigger than that that we would get for a lower bulk modulus.