Why does GPS require a minimum of 24 satellites?

I see six potential reasons for this. You've already mentioned one, the impossibility of "uniformly" distributing the satellites over a sphere, in the question, and percusse and Tim mentioned three more in comments, redundancy, accuracy and visibility on the horizon. Two further aspects are that even with "uniform" distribution over the sphere your averaging doesn't guarantee complete coverage, and the fact that the satellites can't stay in a fixed constellation without being in geostationary orbits.

Accuracy

The accuracy of GPS is higher when the satellites being used are spaced further apart (angularly). One might at first think that that means the accuracy would increase if there are fewer and they're spaced further apart; however, if there are more than the minimum number of satellites in sight, you can choose the outermost ones and get a better angle than if they were all spaced slightly further apart but you had to use the inner ones. Which of these two effects dominates might depend on the details of the configuration.

Horizon

People are usually surrounded by houses or hills or forests; you rarely have a line of sight to the horizon. This post says:

I’m also going to constrain the DOP calculations by requiring that each point on Earth not be able to see any GPS satellite below 10 degrees from the horizon. This is a typical mask angle used for these types of analysis.

To perform your analysis with this constraint, we need to find the value of $\theta$ corresponding to an angle of $\alpha=100^\circ$ between the directions to the centre of the Earth and to a satellite at $\theta$. Applying the law of cosines twice,

$$x^2=r^2+R^2-2rR\cos\theta\;,$$ $$R^2=r^2+x^2-2rx\cos\alpha\;,$$

subtracting to get rid of $x^2$,

$$r-R\cos\theta+x\cos\alpha=0\;,$$

solving for $x$ and substituting it into the first equation,

$$(r-R\cos\theta)^2=\cos^2\alpha(r^2+R^2-2rR\cos\theta)$$

and solving for $\cos\theta$ yields

$$\cos\theta=\lambda\sin^2\alpha-\cos\alpha\sqrt{1-\lambda^2\sin^2\alpha}$$

with $\lambda=r/R$. Substituting $\alpha=100^\circ$ and $\lambda=6370/26600\approx0.24$ yields $\cos\theta\approx0.4$, so $(1-\cos\theta)/2\approx0.3$, so the visible fraction of solid angle would be about $30\%$.

Uniformity

We should first think about what it means for points to be "uniformly" distributed over the sphere. We could try to make the polyhedron formed by the satellites isohedral, isotoxal and/or isogonal. We get the most stringent condition by requiring all three of these properties, which means that the polyhedron is regular, and since it's convex (assuming the satellites are on a sphere), it must be one of the Platonic solids. Obviously there are only five numbers of satellites for which this is possible, but since one of them, $20$, is close to the actual number, $24$, it makes sense to look at this case.

Even if the satellites form a Platonic solid, and are thus as "uniformly" distributed as possible, your consideration of the average doesn't quite give the right number of satellites. This is perhaps easiest to see for the regular tetrahedron. Say our requirement were to always have two satellites in sight, and for simplicity let's assume that we can always see the horizon and the satellites are very far away, so we can see them in exactly half of the solid angle. Then your approach would say that we should need about four satellites "uniformly" distributed at the vertices of a regular tetrahedron to always have two in sight. This is obviously not the case, since three of them can be concentrated in the lower $((-1/3)-(-1))/2=1/3$ of the full solid angle. A numerical simulation shows that in this scenario, about $17.5\%$ of the Earth would only see one satellite, $65\%$ would see two, and $17.5\%$ would see three.

In this simplified scenario, the problem wouldn't occur with any of the other Platonic solids, since they all have opposing vertices so exactly half of them would always be in view. However, going back to the realistic case where we see about $30\%$ of the solid angle, it just so happens that your approach would predict $20$ satellites to be enough to see $6$ of them all the time, so we could try using a regular icosahedron for this case. A numerical simulation shows that in this case $3\%$ of the Earth would see only $4$ satellites, $20\%$ would see $5$, $51\%$ would see $6$, and $26\%$ would see $7$.

So even if we put the satellites on the vertices of a Platonic solid, and even if we could fix them in place (which we can't in these orbits), $20$ satellites would already be cutting it pretty close. If you now take into account that the configuration has to make up for the shifts caused by the movements of the satellites, $24$ is beginning to appear less redundant than it seems at first sight.