This is a difficult question, but I’ll offer my limited insight anyway; perhaps you will find it useful.
One thing that people forget (no accusations made in your direction) is that on the microscopic scale, matter is incredibly chaotic. Even at extremely low temperatures, when electrons start to slow down and settle in lower energy levels, atoms can be expected to experience lattice vibrations, and maybe other phenomena that I’m not aware of.
What this means practically is that it’s terribly hard to actually encode information on an atomic level (bad news for you, homeopaths). When you think about hard drives, or similar media the actual data is encoded on a more macroscopic level, on groups of atoms. Funfact: new generations of Intel processors use 32nm gates – that’s several hundreds of thousands of atoms long.
Armed with that knowledge, we fall back onto less confusing concepts. Solid states of matter experience less chaotic motion than liquids, etc. Therefore, it would be easier to control data on a solid than a liquid. In fact, I’m tempted to assume it would be almost impossible to control a liquid enough to effectively store data on it; so yes, it would be easier to store data on a solid.
I’m not even going to bother thinking about plasma or Bose-Einstein condensate; I don’t know anything about them and assume they’re not very stable.
Note: Thermodynamics is kind of an umbrella term, so yes, it applies here, too.
Note 2: Actually, due to hydrogen bonding you can kind of assume that water has a kind of crystalline structure as well; it fact it can form several different arrangements.
Perhaps I didn’t tell you anything new; but at least you’ll find this reassuring?