What medium does sound travel through best?

Scientifically, this is a very difficult question to answer. The reason is simply that the word “best” is difficult to interpret. In science, understanding the question is often as important as the answer.
You might be asking about the speed of sound. You might be asking about loss of sound (e.g. sound traveling through cotton).
Then again, you might be asking about materials which transmit a range of frequencies with very little dispersion (difference between the wave speeds for various pitches). You might look up soliton waves in narrow channels for an example of a wave that stays together over a long distance.
And yet again, you might be asking about materials which can pickup sound from air; an impedance match.
What materials have the highest speed of sound?
This is the easiest question to answer, so we’ll start with that. In general, the speed of sound in a material varies with the stiffness and mass of that material. Sound traveling through hardened steel will cary much faster than traveling through air. Many materials are characterized by something called a Young’s Modulus. You should find that the speed of sound increases with higher Young’s Modulus. A search for materials with a high speed of sound or a high Young’s Modulus should turn up interesting answers.
One of the most dense materials known is the neutron star. One drop-sized piece of a neutron star has the same mass greater than the giant pyramid at Giza (about a billion tons). Some people calculate the speed of sound in a neutron star to be very close to the speed of light.