Why isn't an infinite, flat, nonexpanding universe filled with a uniform matter distribution a solution to Einstein's equation?
This is a rather subtle question, which confused even Newton. It is very tempting to think that an initially static Newtonian universe with perfectly uniform mass density will not collapse, because the gravitational force cancels everywhere by symmetry. This is wrong.
Here's an analogous question: suppose a function $f$ obeys $$f''(x) = 1$$ and we want to solve for $f(x)$. Since every point on the real line is the same as every other point, we might think that by symmetry, $$f(x) = \text{constant}.$$ But this is completely wrong, because the second derivative of a constant is zero. And stepping back, the whole question doesn't make any sense, because there isn't enough information. To solve a general differential equation, you need boundary conditions.
One possible boundary condition is that the solution looks approximately even at infinity. That's enough to specify the solution everywhere, as $$f(x) = \frac{x^2}{2} + \text{constant}.$$ But now the translational symmetry has been broken: not every point is equivalent anymore, because we have a minimum at $x = 0$. This is inevitable. You can't solve the differential equation without boundary conditions, and any choice of boundary conditions breaks the symmetry.
Similarly in Newton's infinite universe we have $$\nabla^2 \phi = \rho$$ where $\rho$ is the constant mass density and $\phi$ is the gravitational potential, corresponding to $f$ in the previous example. Just as in that example, we "obviously" have by symmetry $$\phi(x) = \text{constant}$$ which indicates that the force vanishes everywhere. But this is wrong. Without boundary conditions, the subsequent evolution is not defined; it is like asking to solve for $x$ given only that $x$ is even. With any set of boundary conditions, you will have a point towards which everything collapses. So the answer to your question is that both the Newtonian and relativistic universes immediately start to collapse; the symmetry argument does not work in either one, so there is nothing strange to explain.
The reason this point isn't mentioned in most courses is that we often assume the gravitational potential goes to zero at infinity (in Newtonian gravity) or that the metric is asymptotically flat (in relativity). But this boundary condition doesn't work when the mass distribution extends to infinity as well, which leads to the pitfall here. The same point can lead to surprises in electrostatics.
We reasoned above in terms of potentials. A slightly different, but physically equivalent way of coming to the same conclusion is to directly use fields, by integrating the gravitational field due to each mass. In this case, the problem is that the field at any point isn't well-defined because the integrals don't converge. The only way to ensure convergence is to introduce a "regulator", which makes distant masses contribute less by fiat. But any such regulator, by effectively replacing the infinite distribution with a finite one, introduces a center towards which everything collapses; just like the boundary conditions, any regulator breaks the symmetry. So, again, collapse immediately begins.
In the end, both the Newtonian and relativistic universes immediately begin to collapse, and in both cases this can be prevented by adding a cosmological constant. In the Newtonian case, this is simply the trivial statement that $\nabla^2 \phi = \rho - \Lambda$ has constant solutions for $\phi$ when $\rho = \Lambda$. However, in both cases the solution is unstable: collapse will begin upon the introduction of any perturbations.
The equation governing the curvature of spacetime in general relativity is $$ R_{\mu\nu} - \frac12Rg_{\mu\nu} = \frac{8\pi G}{c^4}T_{\mu\nu} $$ Or, really, it's $16$ equations in one: $\mu$ and $\nu$ can both take values from $0$ to $3$, representing the four components of any given coordinate system, and for each such choice you get a new equation (with the small caveat that it is symmetric in $\mu$ and $\nu$, so really, it's only $10$ distinct equations).
The symbols $R_{\mu\nu}$, $R$, $g_{\mu\nu}$ and $T_{\mu\nu}$ are so-called tensors, which for now you can think of as real-valued functions on spacetime. (The actual values you get will be dependent on your choice of coordinate system, but if you fix one coordinate system for the region you're interested in they do become just functions. $R$ is a single function while the remaining three, again, are collections of $16$ functions: one for each $\mu, \nu$ pair.)
The left-hand side represents the curvature of spacetime. In flat spacetime we have $R_{\mu\nu} = 0$ for any $\mu, \nu$, and we also get $R = 0$, so the left-hand side will be $0$.
The right-hand side is one big constant multiplied by $T_{\mu\nu}$, which represents the energy at each point in space. In a "sensible" coordinate system (where the $0$-component represents time, and the three remaining coordinates represent space), $T_{00}$ will represent the energy density (including mass density; the other components of $T_{\mu\nu}$ represent things like pressure and momentum density). If there is uniform non-zero mass everywhere, then $T_{00}$ will be non-zero. That means that $R_{00} -\frac12Rg_{00}$ will also be non-zero, which means that we do not have flat spacetime as either $R_{00}$ or $R$ must be non-zero.
In order to regain flat spacetime in this case, and allow both $R_{\mu\nu}$ and $R$ to be zero, it is necessary to add a third term to the left-hand side: the cosmological constant $\Lambda$, giving us $$ R_{\mu\nu} - \frac12Rg_{\mu\nu} + \Lambda g_{\mu\nu} = \frac{8\pi G}{c^4}T_{\mu\nu} $$
Nice question!
Here's a possible statement of the logic in the newtonian case. (1) In newtonian mechanics, we assume that inertial reference frames exist (this is one popular modern way of restating Newton's first law), we assume that such frames are global, and we assume that we can always find such a frame by observing a test particle that is not acted on by any force. (2) In the newtonian homogeneous cosmology, we could assume that the force on a chosen test particle P can be found by some limiting process, and that the result is unique. (This is basically a bogus assumption, but I don't think that ends up being the issue here.) (3) Given that the result is unique, it must be zero by symmetry. (4) By assumptions 1 and 2, P defines an inertial frame, and by assumption 1, that frame can be extended to cover the entire universe. Therefore all other particles in the universe must have zero acceleration relative to P.
In general relativity, assumption 1 fails. Test particles P and Q can both be inertial (i.e., no nongravitational forces act on them), but it can be false that they are not accelerated relative to one another. For example, we can make an FRW cosmology in which, at some initial time, $\dot{a}=0$, but then it will have $\ddot{a}\ne0$ (in order to satisfy the Einstein field equations for a uniform dust). (In this situation, the Einstein field equations can be reduced to the Friedmann equations, one of which is $\ddot{a}/a=-(4\pi/3)\rho$.)
This shows that the newtonian argument (or at least one version of it) fails. It does not prove that there is no other semi-newtonian plausibility argument that explains why an initially static universe collapses. However, I'm not sure what criteria we would be able to agree on as to what constitutes an acceptable semi-newtonian plausibility argument. Some people have developed these semi-newtonian descriptions of cosmology at great length, but to me they appear to lack any logical foundations that would allow one to tell a correct argument from an incorrect one.