What determines which frames are inertial frames? I understand that you can (in principle) measure whether "free particles" (no forces) experience accelerations in order to tell whether a frame is inertial. But fundamentally, what determines which frames are inertial (i.e. what principle selects in which frames free particles will not appear to accelerate)? I've been told that the cosmic microwaves determine the ultimate rest frame of the universe, but that doesn't make sense to me, since one can still ask why that frame is an inertial frame.
Also, I understand that there are no real inertial frames in general relativity, but it seems like there certainly exists approximate inertial frames and we can ask why those frames are approximately inertial and not others. For example, in the frame of a person riding a merry go round, free particles appear to greatly accelerate; while in the frame of someone standing next to the merry go round there are no such great accelerations. Why does the guy (or gal) on the merry go round see free particles accelerating while the other guy doesn't. 
And if you're gonna tell me that it's "the rest of the stuff in the universe" that determines whether the person on the merry go round sees free particles accelerate, I'll ask how you know that all that stuff is not spinning.
I hope this question sort of makes sense, it's been bothering me for a while and my study of relativity (most of special relativity and just the outline of general relativity) hasn't really clarified it for me much.
 A: Well, from the point of view of an inertial reference frame, angular momentum and linear momentum are conserved, and when you aren't in an inertial reference frame, they aren't conserved.
As an example, consider that you are on a spaceship accelerating away from a lone sun.  (ignoring an expanding universe for the moment).  In your frame, the sun is accelerating away from you, without anything to cause such an acceleration.  Momentum is not conserved from your frame of reference, and thus, you aren't in an inertial reference frame.
Hopefully this helps.
A: In general relativity it is the gravitational field that determines which local frame of reference are local inertial frames. I talk about "local" frames because as you observed in your question, there are no global inertial reference frames in curved spacetime.
The gravitational field is represented by a metric tensor field. Given such a metric you can plot the timelike geodesics through any event. These are the trajectories that locally maximise the integrated proper-time calculated using the metric. Anything that moves along such a geodesic is in a local inertial frame.
The cosmic microwave background does not define a preferred frame from the point of view of the equations of motion. It is just one of many reference frames that you can find in the universe by observation. In fact there are many different frames of reference that you could define based on just the cosmic background radiation, and they only coincide in a perfectly homogeneous universe, but the universe is not locally homogeneous. Furthermore these reference frames are in general mostly not inertial frames.
A: 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.
A: In special relativity, the inertial frames are just postulated to exist. There is nothing wrong whatsoever with such an approach: they're frames in which objects will move by constant velocities if no forces act upon them. Newton needed pretty much the same thing to define the laws of mechanics. The important point about relativity (both Galilean and Einsteinian) is that if one frame is inertial, other frames moving uniformly with respect to this inertial frame are inertial frames, too.
This is fully analogous to straight lines in the Euclidean geometry. (Inertial frames are just systems associated with observers whose world lines are straight lines in the spacetime - it's really the same thing in a different space.) Some lines on the paper simply are straight lines while others are not. One could also ask what is the principle that selects which lines are straight. Well, the principle is the set of axioms of the Euclidean geometry. One has to have a system that allows us to say things about the geometric objects - and being able to say whether a line is straight is among the "tools" we have to be given. If we describe the geometry in coordinates that we call Cartesian, then a straight line is given by $ax+by+c=0$.
There is no confusion here unless someone deliberately tries to produce it. Asking who dared to make some systems inertial and others not is analogous to asking why mathematics discriminates against some numbers - because some of them are primes while others are not. Well, mathematics discriminates and it has the full right to do so. It's the very purpose of mathematics - and science - to discriminate all the time. Every time we ask a question, we want to hear the right answer and discriminate against all the other possible answers - the wrong ones. The right answer inevitably discriminates - it treats various objects or numbers asymmetrically. No maths or science could work if someone required the permanent democracy between everyone.
In general relativity, the spacetime is curved and a curved spacetime contains no reference frames - or systems of coordinates - in which the space would look flat. It's simply not flat. So there are no exact inertial frames in general relativity. In general relativity, one may only approximate the notion of an inertial system. One possible definition is that an inertial frame is a good approximation for local phenomena around freely falling objects. If an elevator is freely falling, you may call the frame associated with this elevator "inertial".
However, here on the Earth, it is not the usual choice. We usually say that the freely falling elevator is accelerating i.e. non-inertial. On the contrary, it is the non-falling elevator at rest that is inertial - even though it is not associated with geodesics in general relativity. The choice of the falling elevator has the advantage that you don't have to include the gravitational force among the forces that act on the objects inside the elevator. The only thing you have to include is the crash that will kill you: it's not the free fall but the collision with the ground that becomes your fate. :-)
If you choose that the inertial system is linked to the elevator at rest, you have to add the attractive gravitational force to the equations for all objects on the Earth. Of course, that will make your description of high-velocity phenomena etc. a bit inaccurate. But it's simply the case that curved spacetimes - and nontrivial gravitational fields - can't be exactly described by special relativity (and its inertial frames) only. If this were possible, we wouldn't need general relativity. It's not possible and we need general relativity to describe gravity in the relativistic context.
In the broader cosmic context, away from the gravitational field of the Earth or the Sun, the approximate inertial frames can be defined by the freely moving objects. One of them will be the frame associated with the cosmic microwave background - the frame of spheres such that the total momentum hiding in the CMB photons that are crossing the sphere at each point of the sphere's surface is zero. The CMB frame determines not only what is the vanishing acceleration; it also determines what is the vanishing speed.
With this benchmark in place, one may discuss the motion of the Sun (and the Solar System), our Galaxy, galaxy clusters and superclusters where we belong etc. relatively to the CMB cosmic frame. Those speeds are kind of known. But it's useful to recall that these speeds don't really mean that the Solar System frame is far from inertial. It's because uniform speeds don't spoil the inertial character of the reference frame. So even though the Sun is moving relatively to the CMB frame, by a rather high speed, the system associated with the Sun - and properly oriented relatively to some other galaxies etc. - is inertial with a huge accuracy.
A: In ordinary mechanics, inertial frames are defined by constant-velocity observers. This is still true in GTR--experimentally, "inertial motion" means "no proper acceleration", which can be measured by an accelerometer. The equivalence principle means that at least locally, mechanical systems act like there is no gravity, so on the conceptual level, GTR "inherits" inertial frames from ordinary mechanics, although in a more limited sense.
From the formal perspective, it's exactly as axiomatic as the Euclidean geometry you referenced above. Say you have two curves intersecting at p on a differentiable manifold, and in some coordinates they have same derivative at p, so you say that they're in the same direction. The equivalence classes define the tangent space at p (which can also be done in a variety of other ways), which is a vector space of "directions from p". In particular, the velocity of a particle at some point is just the tangent vector of its curve in spacetime (wordline).
So how do we interpret inertial motion as "having the same velocity"? To do so, we need to be able to compare two vectors between the tangent spaces of different points. Or, equivalent, to be able to transport vectors (and in general, tensors) from one point or another. The mathematical device that lets us do this is called the connection, and like many things in mathematics, it is completely general, with infinitely many possible distict connections on the same manifold. "Inertial motion" or "geodesic" will then just be a curve whose tangent vector stays the same when transported between infinitesimally close points.
Here's where the GTR's postulate comes in. Assume that it is "metric-compatible", which means that the inner product between two vectors likewise unchanged when transported along a curve. Also assume that the connection is "torsion-free", which is a fancy way of saying that if you transport a vector around a small loop in spacetime back to the starting point, then to first order it is unchanged. It turns out that these conditions uniquely determine the connection. (Incidentally, in the second-order change in the loop transport operation defines the Riemann curvature.)
In other words, GTR postulates that the "constant velocity" curves are exactly the length-extremizing curves dictated by the metric tensor $g_{\mu\nu}$. And just like Euclidean postulates, it is quite possible to take a contradictory option. For example, Einstein-Cartan theory of gravity does not have the above assumptions, and in its torsion terms allows spin angular momentum and its gravitational exchange with orbital angular momentum, unlike in GTR.
A: The previous answers have covered every philosophical and epistemological aspect, of the question of inertial reference frames (IRFs), that I could think of. What has not been mentioned is a physical construction in terms of the kinematics of moving bodies. The reference for this answer is Michael Dickson's paper on "Quantum Reference Frames".
This 106 year old construction is originally due to L. Lange ("Ueber das Beharrungsgesetz", Leipziger Berichte 37: 333-351, 1885). Lange's defines an inertial frame of reference as (quoting from Dickson):

a coordinate system in which each of some triple of force-free particles, moving from some common 'origin' in non-coplanar directions, moves in a straight line, the particles traveling mutually proportional distances in equal times. The law of inertia is then the claim that any other free particle will also move uniformly in such a coordinate system.

Once we have this working definition of an IRF, we can easily start to see where it can fail and thus shed light on the inherent physical limitations of the concept. What triples of particles existing in Nature can actually satisfy this construction? Three hard spheres moving inertially in a box with elastic boundary conditions (3D billiards), three celestial bodies - stars or galaxies, three elementary particles - each case defining an IRF on mesoscopic, macroscopic and microscopic scales respectively.
It is clear that each such triple can serve as a basis for an IRF over some finite range of scales. So this discussion immediately suggests that in our non-scale-invariant Universe (i.e. with a hierarchy of scales - stars, billiards, atoms) there does not and cannot exist any single IRF valid on all scales.
For a more detailed discussion I strongly recommend reading Dickson's engrossing article.
A: Yes, there's a very simple, and real good answer to this question, which everyone else forgot to mention. And it applies to both classical mechanics and general relativity frameworks as well.
Inertial frames of reference are the ones in which you feel weightless. Those are the frames in which there's no internal compression on your body, and your path is a geodesic on the field.
The differences all lie within the concepts of proper acceleration and coordinate acceleration. Proper acceleration can be measured absolutely with accelerometers and gyroscopes, while coordinate acceleration depends on the observer.
In more precise terms, in an inertial frame of reference, there are no contact forces, only field forces. When you are in a frame that's only subject to field forces, you just fall through the geodesics of the field (like in a parabolic trajectory in the surface of a planet with negligible atmosphere, or while orbiting a celestial body), you are sliding over the hills of the gravitational field, and thus your movement is inertial.
On the other hand, when you stand on the surface of a planet, or is being rotated in a merry go round, the contact forces of the rigid bodies holding your body make your movement non-inertial.
I have also answered it here, and made an intriguing question here.
A: More than the preceding answers I'd like to emphasize     


*

*a physical standpoint: referring for instance to W. Rindler: "We should, strictly speaking, differentiate between an inertial frame and an inertial coordinate system [...]", together with    

*an explicit operational presentation (not presuming "to know a free particle when you see one", or to accept some "black box as accelerometer just because it says so on the sticker"; but rather indicating a geometric foundation for defining such items), in terms of the principal operational notions of Einstein's applicable thought experiments (briefly: that distinct participants may observe and recognize each other, and that each may judge the order, or coincidence, of own observations).


The aspect in the characterization of an "inertial frame" which I'd like to consider first (for being exemplary) is expressed in the continuation of Rindler's statement: "An inertial frame is simply an infinite set of point particles sitting still in space relative to each other."
A corresponding operational requirement which may be considered as equivalent to what's meant by "sitting still to each other", or at least necessary, would be that for any three distinct "point particle" members (${\textbf A}$, ${\textbf B}$ and ${\textbf Q}$) of the same inertial frame $S$
(1)
participant ${\textbf A}$ finds for each of its signal indications ${\textbf A}_{\mathscr X}$ that
${\textbf A}$'s indication of having seen that ${\textbf Q}$ saw ${\textbf A}$'s indication of having seen ${\textbf B}$ saw ${\textbf A}$'s indication ${\textbf A}_{\mathscr X}$
is coincident to
${\textbf A}$'s indication of having seen that ${\textbf B}$ saw ${\textbf A}$'s indication of having seen ${\textbf Q}$ saw ${\textbf A}$'s indication ${\textbf A}_{\mathscr X}$.
Another important requirement characteristic of an "inertial frame" is that it should have members which are "straight" to each other.
A corresponding operational requirement (which may appear unexpectedly involved, but at least employs notions and operations just as they were used in (1) already) would be that for any two distinct "point particle" members (${\textbf A}$ and ${\textbf B}$) of the same inertial frame $S$ 
(2)
there exists (at least) one additional member ${\textbf J}$ of inertial frame $S$ such that
there exists one member ${\textbf K}$ of inertial frame $S$ (not necessarily distinct from ${\textbf J}$) whereby    


*

*participant ${\textbf A}$ finds for each of its signal indications ${\textbf A}_{\mathscr X}$ that
${\textbf A}$'s indication of having seen that ${\textbf J}$ saw ${\textbf A}$'s indication of having seen ${\textbf K}$ saw ${\textbf A}$'s indication ${\textbf A}_{\mathscr X}$
is coincident to
${\textbf A}$'s indication of having seen that ${\textbf B}$ saw ${\textbf A}$'s indication ${\textbf A}_{\mathscr X}$, and

*participant ${\textbf B}$ finds for each of its signal indications ${\textbf B}_{\mathscr Y}$ that
${\textbf B}$'s indication of having seen that ${\textbf J}$ saw ${\textbf B}$'s indication of having seen ${\textbf K}$ saw ${\textbf B}$'s indication ${\textbf B}_{\mathscr Y}$
is coincident to
${\textbf B}$'s indication of having seen that ${\textbf A}$ saw ${\textbf B}$'s indication ${\textbf B}_{\mathscr Y}$.
Requirements (1) and (2) also have bearing on the characterization of members of the same inertial frame $S$ as "not spinning around each other". Various ways of strengthening these requirements may of course be considered.
The (seemingly) ultimate requirement arises from considering relations between different inertial frames: ($S$ and $F$):
the requirements of characterization of one particular inertial frame ($S$, with members ${\textbf A}$, ${\textbf B}$ and others) should be strong/specific enough such that
(*)
if some other participant, ${\textbf V}$, who is not a member of inertial frame $S$ (due to failing requirements such as (1) or (2) wrt. ${\textbf A}$, ${\textbf B}$ or other members of $S$) but who "met certain members of $S$ in passing"
is (nevertheless) identified as member of an inertial frame $F$ other than $S$ (due to ${\textbf V}$ satisfying all applicable requirements wrt. suitable participants other than ${\textbf A}$ or ${\textbf B}$ and so on)
then ${\textbf V}$ "moved uniformly" (straight and with "constant speed") among the members of $S$;
and all other members of inertial frame $F$ as well, with the same "speed" value as ${\textbf V}$.
(A relevant notion of "parallelism" or "the same direction of motion as ${\textbf V}$" only arises in the course of the stated requirement being satisfied.)
Of course, this refers to a notion of "speed" values for which an operational definition hasn't been stated here yet. It shouldn't be surprising, however, that the relational requirement (*) can not be satsfied if only sets of participants are being considered which are all "straight" to each other in the sense of requirement (2). This necessitates the consideration of sets of participants whose geometric relations "extend in more than one dimension".
A sufficient requirement (or rather, one more characterization of an "inertial frame" to which a corresponding operational definition can be constructed so that the relational requirement (*) finally can be satisfied) happens to be
(3)
that the members of the same inertial frame $S$ are "flat" to each other. (Describing a corresponding operational definition is cumbersome.)
Accordingly, it is not hard to construct examples of sets of events with "geometry" (causal relations) such that it would not contain any set of timelike worldlines (one for each participant) at all that would be strictly "sitting still to each other" and "flat to each other"; but only to some approximation.
