"...What balances the electron degeneracy pressure in a solid?..."
The problem with this statement is that it assumes that the "electron gas" is exactly analogous to, say, Helium in a balloon. We need to (in my opinion) find slightly different ways of thinking of Pressure of a solid, as against pressure of a fluid.
Helium in a balloon is a fluid. What that means is that if we say that the Pressure of a Helium balloon in equilibrium with its surroundings is $P$, then, we can conclude that the pressure in the "atmosphere" surrounding the balloon must also be $P$. The fact that we are dealing with something that is able to flow implies that unless balanced by an equal and opposite pressure, the fluid will "spread" till its pressure equals that of its surroundings.
Let us now compare this with the situation you describe. That is, a lattice (a rigid solid, definitely cannot flow); On this background, a "sea" of nearly free electrons. Obviously, this whole setup is in equilibrium as we see it, notwithstanding any Pressure it has.
Note that we may bring in atmospheric pressure into this, but I think that is misleading. I am pretty sure a piece of metal (which is an example of a crystalline solid with a degenerate electron gas) won't disintegrate if it is placed in a vacuum.
So how should we think of pressure in a solid? Strictly speaking, using the thermodynamic relation $dE = -PdV$ ; ie., Pressure is the rise in Internal energy of the solid per unit volume of compression. If we compress/stretch the solid, then energy rises/falls by $P$ per unit volume. Compare this with the physical implication of pressure of a fluid above. Solids deform via intentionality. Fluids, in contrast, deform spontaneously, just because they can flow.
Seen in this way, it is obvious why the electron-gas should have a "Pressure". If we compress the system, we are changing the boundary conditions for the electronic states, (occupied by the electrons forming the gas) and hence its internal energy. In short, Pauli exclusion principle ; the energies of the levels change, but their occupation numbers can't (at absolute $0$), so the total energy changes.
Also, note that this is not the only source of "Pressure" in this system. Obviously, the rigid lattice has its own associated pressure as well. But none of this means that this needs to be balanced by external pressures in order for it to be in equilibrium.
Addendum, on nomenclature: The exchange of comments below also made me realize, that the nomenclature of electron gas or fluid may be confusing. An electron fluid is so called because it is fluid with respect to transport of energy, charge, spin, etc (whatever the electrons can transport). But an electron fluid is definitely not to be thought of as fluid with respect to mechanical deformations. If I had to say what the other answer is saying (from what I understand), is that the reason the electron fluid does not require an external pressure to hold it together is the attraction of the ionic lattice. Frankly, I find this a little confusing, because the fluidity of a so called electronic fluid is very much an emergent phenomenon specific to this special situation of electrons on a lattice. What I mean is, normally, one starts with a tight-binding model, then takes the long wavelength (low energy) limit ; then, a fluid emerges. I don't know how to make sense of this outside of this specific context.
So, the safest thing to say, it seems, is that the electron fluid is not fluid in a mechanical sense because it is tied to a mechanically rigid elastic medium (the lattice). How exactly it is tied is not at all a factor in the behaviour of the electron fluid. Remember, that the tying of free electrons to the lattice happens on the length scale of the lattice. The fluid emerges at a much larger lengthscale, by which point, the exact nature of the underlying rigid lattice is irrelevant. All that matters is the fluid is tied to some elastic solid, so its mechanical deformations are constrained to this unspecified background solid. That is all that is required to explain why the degeneracy pressure of the electron fluid is not to be thought of as something that needs to be counterbalanced by an equal and opposite pressure to prevent the electron fluid from flowing out.
Addendum (2): A comment points out below, the "nearly free electrons" is a poor approximation : It is more subtle that that ; In most normal metals, the nearly free electron model IS a very good model of the macroscopic properties of what we see (with renormalized parameters, of course). That is why the Boltzmann equation works so well in calculating transport coefficients in normal electron fluids. (leading to the Fermi - liquid theory). Of course, this fails sometimes, in quantum critical systems, which is when we have various kinds of Non-Fermi liquid behaviour. These phases are marked by the absence of quasiparticle excitations of any kind. Hence, it is objectively true in these situations that the model of nearly free electrons is a poor one to explain the macroscopic properties we see. But normally (in the aptly named normal fermi liquid phase) , the nearly free-electron model is an astonishingly good one (again, to explain macroscopic properties of the fluid)