What is the most basic system that exhibits states of matter?

Two atoms are definitely not sufficient to tell the difference between a liquid and a solid. The difference between those states is that the structure of a solid remains effectively fixed while a liquid's changes. With a single bond, there's no reasonable way to separate those two cases.

As mmesser314 pointed out in concepts, gas liquid and solid are terms used to describe systems where there are enough atoms that we cannot meaningfully keep track of all of their states.

• In a gaseous system, if you know the state of an atom at t=0, you very rapidly lose track of its state due to all of the random collisions. In a reasonably short period of time, you don't know where the atom is inside the container.
• In a liquid system, if you know the state of an atom at t=0, you still lose track of it rapidly. However, you can be quite confident that the atom is in the bottom part of the container, because that's where the liquid atoms all are congregating due to gravity.
• In a solid system, if you know the state of an atoms at t=0, you can generally predict where it is going to be in the future because the atomic bonds are so rigid.

Of course these phases are really just heuristics. They're not fundamentals of a system, but rather patterns that tend to occur with normal systems that we see on a day to day basis. As an example of this breaking down, consider dopant drift. When making Central Processing Units, we embed "dopants" which change the properties of the silicon. We do this at an incredibly fine level, on the order of nanometers. We rely on the atoms to stay in place, because this is a solid. However, if you run the CPU hot enough for long enough, you observe dopant "drift," where the dopants eventually move a few nanometers this way or that. This can eventually destroy fine structures on a CPU and ends its life. But note that we are talking about nanometers here.

And as for your question about temperature: temperature is important. It is a measure of uncertainty in the slow trajectory of the particles. If you know where everyhting is, you don't bother modeling it as a solid, liquid, or gas. You just model it as a bunch of particles and leave it at that. The more you are uncertain about states, the more you want to be able to categories the systems as phases of matter.

Well, for the "State of Matter" to really be something fundamentally physical, it really should be possibly to define it as an interaction of just two atoms.

If you dive in to the depths of this, you soon notice that Pressure and Temperature can finally both fully be defined through particle mean velocity; $v_{rms}=sqrt{{3k_BT}/{m_p}}$

Then we can also calculate the Mean Free path of any particle by equation $1/lambda=sqrt2pi d^2n_v$

Then we if we have some good idea about the diameter of the particle, we might find out that this all leads to very fundamental constants and the states of matter can be derived from the speed of light.

This then tells us that there is no fundamental difference between fluid and solid, and the can be just considered as a "condensed matter".