As you say, there's a perfectly sensible operational definition of an inertial frame: it's one in which free particles move with constant velocity. Even in general relativity, it makes sense to talk about inertial frames, but only locally. To be precise, an inertial frame is well-defined only in an infinitesimal neighborhood of a spacetime point, although in practice it's a sensible approximation to extend such a frame to a finite neighborhood, as long as the size is small compared to any length scales associated with spacetime curvature.
The fact that there are inertial frames is essentially an axiom of general relativity. The theory is based on the idea that spacetime has a certain geometric structure, which allows for the existence of geodesics, along which free particles travel. Within a sufficiently small neighborhood the geodesics near a given point "look" to a good approximation like what you'd get in an inertial frame.
So there's not really a good answer to the question of why inertial frames exist: it's just part of the assumed framework of the theory. But that's not quite what you asked. You asked if there's a reason why a given frame S is inertial and a different frame S' isn't. It sort of depends on what you think would count as a reason. For a given spacetime geometry, the geodesics are well-specified (as solutions to a certain differential equation, or as curves that have certain geometrical properties). The inertial frames are the frames that make the geodesics look like straight lines. It's all terribly mathematically well-defined and self-consistent, but it may not have the intuitive feel of a "reason why."
You mention the possibility that the reason is "all the other stuff in the universe." As you may know, this idea has a noble pedigree: it goes by the name of Mach's principle. Einstein was apparently quite enamored of Mach's principle when he was coming up with general relativity, and he would probably have been very happy if the theory had the property that the inertial frames were determined by all the other matter in the Universe. But general relativity's relationship with Mach's principle is complicated and problematic, to say the least. For instance, good old flat Minkowski spacetime is a perfectly valid solution to the equations of general relativity. That solution has well-defined inertial frames, even though there is no matter around to "cause" them.
Yes, the (any) inertial frame is unaccelerated relatively to any other inertial frame. The previous sentence, if it were the only thing we could say, would be a circular definition of the inertial systems of a sort. But given one inertial frame, it would still be enough to find all the other inertial frames.
You should view the situation as follows: Newton's theory or, analogously, Einstein's special theory of relativity postulates that there exist inertial frames. We may also say that it's those in which all the objects that are unexposed to any forces remain in a uniform motion in the same direction. One may see that the previous sentence implies that there exist infinitely many inertial frames; and they're in uniform unaccelerated motion with respect to each other.
All other frames, those that are not in uniform unaccelerated motion in the same direction relatively to an inertial frame, are non-inertial and according to these frames, objects may move along curved or accelerated paths even if no forces act upon them.
Best Answer
Imagine a point mass attached to ends of six identical springs of relaxed length $L$. The springs are oriented in co-linear pairs, with these pairs mutually perpendicular to the other pairs, i.e., they form an $(x,y,z)$ coordinate system. Attach the other ends to the walls of a cube of dimension $2L$.
If the mass remains in the center of the cube, the cube is in an inertial reference frame.