If liquid and gas are both chaotic states of matter, what's the difference between them on the molecular level?

Everything you've said is correct, which is why the conclusion is: there is no fundamental difference! Under the modern classification, they're just the same fluid phase of matter.

For example, consider the phase diagram of water. If you take water vapor, slowly heat it up, then pressurize it, and then slowly cool it down, you'll end up with liquid water. This entire process is completely smooth. There isn't any sharp point, like a phase transition, where the behavior qualitatively changes; thus we can't make a sharp distinction between liquids and gases.

There are fluids that are "liquid-like" (densely packed, strong interactions between neighbors) and fluids that are "gas-like" (sparse, weak interactions between neighbors) but no dividing line, just like how there's no moment where a shade of grey changes from white to black.

By contrast, ice really can be distinguished from liquid water or water vapor. You can't turn either of the two into ice without crossing a phase transition. At that point, the atoms will suddenly become ordered, and you can see this from a snapshot of their positions.

---

Edit: in response to the 25 comments, I'm not saying there's no difference between liquids and gases, I'm saying that there are clearly liquid-like things, and clearly gas-like things, but a continuous spectrum between them. Here are some properties that characterize gases:

• large distance between molecules
• weak interactions
• large mean free path
• high compressibility
• very low surface tension
• upward density fluctuations at small separation

The opposite properties characterize liquids. In the easy cases, you could use any of these to make the call. But all of these properties change continuously as you go from one to the other, as long as you go around the critical point. This isn't true for a solid/liquid or solid/gas phase transition.

The described measurement would allow you to construct the Radial Distribution Function, the probability of finding another particle a distance r from a reference particle usually given as g(r), which has a unique signature for each phase.

The plot below from https://en.wikibooks.org/wiki/Molecular_Simulation/Radial_Distribution_Functions shows g(r) for argon in different phases.

Argon of course does not have strong interactions you might be tempted to argue this is a trivial case of an ideal gas vs. a close-packed liquid but that would be incorrect. A real gas only has one peak (called a coordination sphere), while a liquid will have multiple peaks. All of this is very nicely explained in the link above.

Also note in the image provide the x-axis is normalized by $\sigma$ which is the molecular diameter meaning that this measurement is scale invariant and satisfies the conditions laid out in the question.

EDIT:

In response to this question about the phase transition there certainly is a phase transition between liquid and gas and the mechanism is nicely described and modeled in the link in the comments from @EricTowers, http://rkt.chem.ox.ac.uk/lectures/liqsolns/liquids.html, a quote from there referencing a applet that lets the user play around with different conditions in a molecular dynamics simulation, which is used to model these systems.

"(iv) With the density at its minimum lower the temperature and you will see that the atoms start to form small clusters (this takes some time). On the limited scale of the simulation this is condensation to form drops of liquid. It makes it clear that the attractive forces are responsible for the formation of the liquid state. "

This plainly describes the process of the transition, in this case, from gas to liquid. The transition occurs when the thermal energy in the molecules can no longer overcome the inter-molecular forces and the molecules begin to 'stick' together, condensing. To go from liquid to gas, the opposite happens and the thermal energy is sufficiently high that the inter-molecular forces cannot make the particles stick together. This is the reason for the bumps in the graph shown in the answer, and why gases have one coordination sphere that decays as a function of distance. The details of the gas radial distribution function tell you about the inter-molecular forces but there is no sticking, so there is only one bump.

In a gas the molecules move separately. In a liquid they cling together due to van der Waals forces which are strong enough that the vibrating molecules do not completely separate.