I'm going to argue that the distance between molecules does generally increase with temperature for very fundamental reasons, although normal ice (Ih) and liquid water are an exception. At low temperatures, substances minimize their energy, which usually results in ordered crystalline arrangements. At high temperatures, substances maximize their entropy. That is, at high temperatures everything is as random and mixed up as possible.
Assuming that you have some empty space, there are more ways to put two molecules far apart than there are to put two moleucules close together. You can see this in the diagram below. There are more ways to place a second molecule in the blue spherical shell, at a long distance from the central water molecule, than there are to place water molecules in the orange spherical shell, at a short distance from the central water molecule. In fact, the number of ways to place the second water molecule increases with the volume of the spherical shell, that is like 4πR2, where R is the distance between the molecules. So, the state where two water molecules have a long distance between them has a larger entropy than the state where they have a short distance between them.
Simply due to geometry, at high temperatures, molecules will tend to be far apart. Water boils at high temperature simply because there are more ways to scatter water molecules throughout the whole kitchen than to place all of the water molecules in the pot. Most substances become gases at high enough temperatures given sufficient empty space. Most substances expand as their temperature rises.
Adding distance between molecules is not the only way to increase entropy, which accounts for the exception of melting ice. Entropy can also increase by making the arrangement of molecules and their orientations more disordered. Liquid water has more entropy than ice not because the molecules are farther apart, but because they arranged and oriented more haphazardly.