Why are phase transitions discrete? It seems like there is no "in-between" for the phases of matter; it can be "solid" or "liquid", but what about the in-between? 
Why is there no spectrum of matter between the phases (e.g. a range of states between fully liquid and fully solid)? Why are the phase transitions discrete?
 A: This is a very interesting question. My first instinct is to say that they are, by definition, sharp changes in the form of the distribution of probability of microstates, that occur even for small changes in the macrostate. So, there are plenty of examples of physical systems where changes happen gradually. Phase transitions are the ones where they don't, by definition.
The Ising  example
I'm guessing this answer won't satisfy you, and it doesn't satisfy me either. So, let's have a look at the simplest example I can think of, the all-to-all Ising model without an external field. Here, every spin $i$ has a lower energy if it's aligned to average field of the others, and a higher one if it's anti-parallel to it.
$$ H_i = -Jm\sigma_i $$
where $\sigma = \pm 1$ is the spin direction, $J$ is a positive constant, and $m$ is the average field that the spin "feels". Now, the point is that this $m$ is itself generated by the other spins:
$ m = \sum_j \sigma_j.$
You can see, then, that there is a non-linear self interaction of the group of spins. Without going into the details (you probably know them  already), it turns out that there's an equation for $m$:
$$ m = \tanh(Jm).$$
It's easy to see that this has 0 as a trivial solution; however, it also has two additional solutions (as you can see by plotting both sides of the equation) when $J>1$, and these happen to be stable. This shows why there is a phase transition in this system. For $J\leq 1$, there is one solution. For $J>1$, there are two. There is no such a thing as "one solution and a half", of course, so this is necessarily a discontinuous difference.
So my second answer is: it descends from the weirdness of certain nonlinear equations that govern the system. This is also related to the mathematical concept of bifurcation.
Landau theory
Having a look at Landau theory helps us understand how something similar happens in general. Consider a physical system described by an order parameter $m$ (corresponding to the magnetisation in the case above). We can write its free energy as a function of $m$ and of the temperature $T$. Furthermore, let's assume that we can approximate it as follows (it's just a fourth order in $m$ around 0, and $\alpha$ is expanded at first order, details here):
$$ f(T) = f_0(T) + \alpha(T-T_c)m^2 + \frac{\beta}{2}m^4. $$
The equilibrium $m$ is given by the minimum of free energy:
$$ \alpha(T-T_c)m + \beta m^2 = 0,$$
which has one real solution when $T>T_c$: zero; and three solutions when $T<T_c$, analogously to what I showed above.
The picture below shows how one minimum of the free energy turns into two:

Symmetries
Another way of putting it is connected with the concept of symmetry. The disordered phase has a higher degree of symmetry than a state of the ordered phase: an Ising model with zero magnetisation is invariant under up/down flipping of the whole system; a non-synchronised Kuramoto model has undefined average phase of its oscillators, which gives it $U(1)$ symmetry.
However, once the oscillators synchronise, they will have a given global phase. When the spins align, they may randomly align in the "up" or the "down" direction, but they have to collectively choose one. This is referred to as spontaneous symmetry breaking. As far as I know, symmetries can't be half-broken.
Gas/liquid/solid
I don't know enough about these transitions to tell you about the physical details, but my guess is that something analogous to what I described above also happens in this case. However, these are first order transition, which follow different formalisms, and I'm not familiar with their Landau theory. Some interesting points about those are made in this answer to a different question.
I hope this gives you some intuition.
A: Phase transitions represent transitions between different phases of matter and these phases are distinct. Unless one considers the Kosterlitz-Thouless phase transitions, phase transitions separate phases that have different symmetries. As a result a phase transition represent the point where symmetries become broken.
Symmetries are either present or absent. There is no spectrum between the two where they are only partially present. That is why the phases on the opposite sides of a phase transition are distinct.
The way we see this is to look at a particular quantity that does not respect the symmetry. This is called an order parameter. On the one side of the transition where the symmetry is present the order parameter is zero. On the other side the order parameter is not zero, indicating the presence of this quantity (a nonzero vacuum expectation value), which breaks the symmetry (or at least shows that the symmetry cannot exist).
It doesn't matter whether one considers a first order or second order phase transition. The only difference in this case is that the order parameter either jumps from zero to some nonzero value at the phase transition (first order), or it grows from zero starting at the phase transition (second order). In both cases, the function of the order parameter as a function of the control parameter is non-analytic at the phase transition point. The nonzero value of the order parameter indicates that the symmetry is broken, making it distinct from the situation on the other side where the symmetry is in tact.
A: The important point is whether you look locally or globally on a phase transition.
For instance, if you only look locally on different phase transitions, it is always distinct. From the conventional phase transition theory, different phases have different symmetries, e.g. solid breaks continuous translation symmetry, while liquid doesn't break it. So a state can either break it or not, which means locally it can either be solid or liquid.
But if one looks globally on a physical system, the story is a bit different. It relates to the correlation length of the phase transition. For first order phase transition, the correlation length is finite, i.e. solid-liquid transition is first order, so there exists mixture of solid and liquid during phase transition. For second order phase transition, the correlation length is infinite, i.e. paramagnet-ferromagnet transition is second order, so a material can either be ferromagnet below Curie temperature and paramagnet above Curie temperature.
Of course it is a very complicated matter at the transition's critical point, e.g. at Curie temperature. A gapped system would be gapless at critical point, bringing conformal field theory relevant.
A: *

*An isolated thermodynamical system (system with fixed energy E) spontaneously settles in a state of maximum chaos. This is the second law of thermodynamics. Max chaos means max entropy.


*A system in equilibrium with a thermal reservoir spontaneously settles in the state of minimal free energy (so that the entropy of the system + reservoir is maximal). For a system with fixed temperature, Helmholtz free energy = E - TS is minimal; if pressure is also fixed, Gibbs free energy E - TS - PV is minimal.


*The discrete phases are the states with local minima of free energy. Intuitively (or just logically), it is acceptable that a "continuous classical system" may have discrete minima.


*It turns out from the observations that the same substance can have several stable states, such as solid, liquid, gaseous, etc. The phase transition happens when an order of minima changes. For example, when the minimal free energy of water becomes smaller than the free energy of ice, ice melts. (And a triple point is where three minima coincide, etc.)


*Other answers mention symmetry. Yes, certain states possess symmetry, which may explain, for example, the existence of several solid phases of the same substance. But this is not relevant to the question of the discreteness of phases.
