Why are phase transitions discrete?

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.

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.