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 $f(a) = f(-a)$ for some large $a$. 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, as 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 an even number. Any set of boundary conditions will break the symmetry and imply collapse.
For example, dropping irrelevant constant shifts, imposing spherical symmetry about the origin gives $\phi = \rho r^2/6$ which implies collapse towards the origin. Imposing spherical symmetry about a point $\mathbf{a}$ gives $\phi = \rho |\mathbf{r} - \mathbf{a}|^2 / 6$ which implies collapse towards $\mathbf{a}$. And imposing translational symmetry in the $x$ and $y$ directions and symmetry over flipping $z$ gives $\phi = \rho z^2/2$, which implies collapse towards the $z$-axis.
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 set towards which everything collapses; just like the boundary conditions, any regulator breaks the symmetry.
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.