If all motion is relative, how does light have a finite speed? I've often heard that Einstein shattered the notion of absolute motion (i.e. all things move relative to one another) and that he established the speed of light as being absolute. That sounds paradoxical to me; I cannot understand how the two concepts can be reconciled.
Before going further, I'd like to say: 1) Over the years, I've seen many layman's explanations on these topics (including the nice YouTube video by Vsauce, Would Headlights Work at Light Speed?). I understand everything that's said (or, at least, I think I do). Just nothing I've found seems to address this apparent contradiction. 2) More recently, I've tried to find the answer on my own. That includes searching the posts on this site. Some come close (like this one), but nothing I've been able to find seems address specifically what I'm asking.
Back to the question:
Relativity shows us that there is no universal frame of reference by which to judge motion, so object A might be reckoned as moving at 10 m/s relative to object B or as stationary relative to object C. This is fine for me. I can grasp that the universe has no intrinsic coordinate system, that we only think that way on Earth because we have the ground to move over.
Then there's the speed of light (in a vacuum). The speed of light is the ultimate "speed limit," it's often said. But if there is no universal frame of reference, how can there be any such speed? The very idea only make sense if there is a universal frame.


*

*If one object is moving (uniformly) at 60% c and another object is also moving at 60% c, but in the exact opposite direct, then from the perspective of either one (if they could still see each other) the other would appear to violate that speed limit.

*All these spacetime bending consequences used to explain why nothing can move past this speed only seems to enshrine the concept that there is some ultimate speed standard.

*If there is only relative speed, then the concept of light having a specific speed in the vacuum should be a nonsensical one since it having speed (x m/s) would only make sense when measured against some other body.


Since I was very young, it has always sounded to me like motion is only mostly relative, that until you get close to the speed of light, the effects of an absolute frame of reference are negligible. Perhaps that there is an actual fabric of space which everything moves relative to, which is why there is something to expand between galaxies (faster than light can propagate) in the metric expansion of space. Growing up, I always thought this would just start makes sense with time. Now I'm up to a first year (college) level in physics, I even know basic calculus, yet I'm still hopelessly confused.
EDIT: 
Thank you to whoever suggested this may be a duplicate of What is the speed of light relative to?. It and others are very much related and at least partially answer my question. Unfortunately, explaining that distances become shorter and time becomes slower as a way to stop you from exceeding the speed of light does not explain how that speed is not an absolute.
By my reckoning, if all speed is relative, then no matter how fast you go light should always race away from you at the same apparent speed. I.e. there should be no speed limit. For there to be a speed which you cannot exceed or you would catch up (and make time irrelevant) requires the very concept of some external speed by which light can travel and nothing else can reach - thus my logical paradox continues unabated.
 A: First:  Maxwell's equations predict that the speed of light is absolute.  The whole motivation for the special theory of relativity is to reconcile this with the notion that all motion is relative.  In other words, you're worried about exactly the same thing that troubled Einstein.  You just haven't understood how he solved it.
The key to your confusion is right here:
If one object is moving (uniformly) at 60% c and another object is also moving at 60% c but in the exact opposite direct, then from the perspective of either one (if they could still see each other) the other would appear to violate that speed limit.
This isn't true.  In fact, from the perspective of either one, the other is moving away at a speed of about $.88c$.  Of course you, standing on the ground, will claim that they are moving away from each other at $1.2c$.  This is possible because observers in motion relative to each other will disagree about things like the distance between two events and the time between those events --- and therefore will disagree about the speeds at which things are moving away from each other.  Special relativity tells you exactly how to calculate those disagreements.
A: Gennaro Tedesco's fantastic answer shows how the speed $c$ comes to mean the maximum speed that cause-effect links can propagate, relative to any observer. 
To, to sum Gennaro's answer up to answer your title question, the velocity concerned is the speed of cause-effect propagation relative to the observer's rest frame. It measures how long it takes to cause-effect to propagate between experimental kit at rest relative to the observer in his or her rest frame laboratory. If you're controlling apparatus at rest relative to you a distance $d$ away from you in your rest frame by remote control, it will take time at least $d/c$ for your control signal to reach the apparatus, and this minimum delay per unit distance $c^{-1}$ is the same for all laboratories in inertial frames.
A: (originally a comment, but it's getting a bit long, so...)
Try the VSauce video again - it does actually explain the matter. Try the bit from 3:00 to about 4:30 a few times, and think hard. One of the tricky parts about Relativity is that you need to hold a lot of concepts in your head at once - you really need to understand every part to get rid of the confusion. There's nothing really special about light - it behaves the same way any other mass-less entity behaves. And that includes the fact that any observer, no matter his frame, perceives the speed of light (the speed of information) to be the same. It's really a property of the space-time itself, not something in the space-time. You might want to ask why mass-less particles in particular behave this way in general, but that'd be a rather big new question :)
To address your edit, this is exactly the point about all the observers agreeing on one speed of light. As far as the ship-based observer is concerned, there actually isn't a finite maximum speed - they can accelerate ever faster (provided they have enough fuel), and due to time-dilation (which is not a simple trick, it's critical to understanding relativity), they will be moving ever faster - as far as they can tell. From an observer on, say, Earth, they will be simply moving close to the speed of light, but to themselves, they can be going 1000c or whatever.
The language is a bit confusing, especially when you only stay on the surface - ideas like "relative" and "absolute" have a slightly different meaning than you might think in the Relativity world we live in. "Absolute" is something all observers agree on. "Relative" is everything else.
So everyone can agree on one single speed of light - from any point of view, light always travels at the same speed. However, that's pretty much the only thing they agree on - hence the misleading quote "everything is relative". So, why does that mean that we can't go around colonizing stars with a warp drive? After all, the observer on the ship can observe himself moving at 1000c (ignoring the fuel costs and other complications), so where's the "speed limit"?


*

*Ship A travels to a distant star at 1000c, and it takes a month to get there, as far as the crew is concerned.

*Ship B travels the same trip a month later - again, the crew perceives a single month going by, and the crew of ship A perceives B's arrival a month after A arrived (two months after A launched, as far as A's crew is concerned).


Huh? That's the warp drive, isn't it?! Nope. The problem is the trip back:


*

*Ship A travels back home, again at 1000c. It takes another month, making the whole there-and-back-again trip three months long.

*On the Earth, though, this took about 3000 months - from Earth's POV, the ship never travelled faster than light. Hence, the Twin Paradox.


If you only care about colonizing and exploring the galaxy, the only problem relativity brings is the cost of accelerating fast enough with respect to the source and target (and slowing down again). Return trips are the tricky twin-paradox, time-dilating kind. But this also seems to be the way space-time works. No matter what clever trick you use, you can't really get around this - if you used a "traversable wormhole", you'd again be travelling at much higher speeds than c as far as you're concerned, but as soon as you got back to your point of origin, you'd find that the trip took a lot longer than you thought - you never travelled faster than c with respect to your starting point. This is a fundamental building block of the whole theory of relativity - the way space-time works. It's hard to see how you could "fix" relativity while keeping the confirmed observations - as the saying goes, "Special relativity, causality, FTL - pick any two".
Also, don't forget that the c ~= 300 Mm/s is just a matter of units. It makes just as much sense to say that c = 1, and derive all the other units from that - in fact, it's rather practical for some applications.
A: I'd like to add a little to GreenBeans wonderful answer that not everything is relative. He makes a few points at the end of his/her already long answer hurriedly (not meant as a criticism):

...it is a choice[, ]a choice of coordinate system[?] There are many coordinate systems in which the speed of light is not constant, or even depends on the direction. So, is that it? It's a definition? That is not a very satisfying answer, and not a complete one. What makes relativity work is the amazing fact that this choice is even possible.

and further on ...

... If we design our coordinate system to describe space isotropically and homogenously and describe time uniformly ...

We sometime forget in relativity and in differential geometry that there is still an objective reality in co-ordinates, however bizarrely and human-centrically they may be defined and even though we think of them as human constructs. At least in physics, for co-ordinates to be useful, there must be an objective, physical procedure for finding the physical point in spacetime labelled by given co-ordinates. Let's look at this objective, nonrelative physics.
To use GreenBeans' words again, the choice that makes an invariant $c$ possible and gives it physical meaning is the choice of affine co-ordinates. Roughly, these are co-ordinates defined by the of rational multiples of displacements along linearly independent directions in space and time of uniform intervals marked out by unit measuring rods and clock ticks in each of the inertial frames. Physics enters our geometry insofar that we make the physical postulate that the Euclidean geometrical notion of "straightedge" (more generally, geodesic segment) and the idealized constructions, defined by Euclid's postulates, of marking out a rational number times a unit length along a straight line are a good mathematical model of what we do when we take a ruler and do the same. This is an experimental, objectively testable result. Likewise, the time co-ordinate enters an analogous description by marking out rational multiples of unit "ticks", where the ticks are defined either by Einstein's procedures with light, or, one can use the definition in Chapter 1 of [1] that "uniform" ticks are ones that the make the motion of a body uninfluenced by forces look uniform from an inertial frame.
There is another piece of objective, nonrelative physics essential to the invariant speed concept and that is Galileo's principle: the notion that an observer that there is no measurement that an observer in an inertial frame can do from within their own frame that can detect the observer's motion relative to any other frame. This is most poetically described in Galileo's own 1632 Allegory of Salviati's Ship within his famous "Dialogue Concerning the Two Chief World Systems" (the one that got him into heaps of trouble with Pope Urban II when the latter, having a bad hair day, got a bit bolshie at the implied slight on Papal Infallibility). 
Once you accept Galileo's relativity postulate as a piece of objective, reproducible, nonrelative physics, this means that co-ordinate transformations between inertial frames must form a group (there's a little bit more to this assertion, as I show on my website [2] and also in a hopefully (subject to review) a forthcoming EJP article). So a general transformation on co-ordinates $X$ is of the form $X\mapsto f(T,\,X)$ where the transformation $T$ belongs to a group and $f$ is the group's action on the co-ordinates. Then, once you accept that affine geometry models real systems of surveying procedures and time measurement, then the Copernican notion that Nature doesn't care where we put our origin translates to 
$$f(T,\,X_1+Y) - f(T,\,X_2+Y) =f(T,\,X_1) - f(T,\,X_2)$$
i.e. the affine components of vectors linking two spacetime points with affine co-ordinate $X_1$ and $X_2$ are unaffected by an arbitrary shift $Y$ of origin. It then follows that the group action fulfils the equation:
$$h(X+Y) = h(X)+h(Y),\text{ where }h(X)\stackrel{def}{=}f(T,X)-f(T,0)$$
which is Cauchy's famous functional equation. There is one and only one continuous solution to this equation and that is $h(X) = \Lambda\, X$, where $\Lambda$ is a matrix. So if we make the further physical postulate  that co-ordinate transformations are continuous, then:
$$\text{Galileo's Postulate } + \text{Copernican Spatial Homogeneity Postualte }+\text{Continuity of Transformation Postulate} = \text{Co-ordinate Transformations Between Inertial Frames Form a Matrix Group }\\\text{Acting Linearly on Affine Co-ordinates}$$ 
The physical postulate of continuous transformation encodes the everyday experimental result that, as we ride on a bus, we see trees and walkers in the street as we pass even though the bus is moving: we don't see their images shattered into disconnected chaotic sets!
Another active user on this site, Benjamin Crowell, has a wonderful description about how affine geometry with metric structure leads to the Lorentz transformation and the invariant speed concept in chapter 2 of his general relativity book[3]. The following is my own take on it. 
If we further postulate that there are collinear motions that are descibed by a matrix group parameterized by a real parameter such that group composition is a continuous function of this parameter, then the only transformation group in keeping with this physical postulate as well as Galileo's, Copernicus's and Transformation Continuity is of the form:
$$\mathfrak{L} = \{\exp(\eta\,K)|\,\eta\in\mathbb{R}\}$$
so any co-ordinate transformation $\Lambda$ transforming the spacetime co-ordinates between inertial frames belongs to a group of $4\times4$ matrices this form, where $K$ is a constant matrix defining the direction of motion and $\eta$ is a generalized swiftness parameter, called the rapitity. Just think of it as a speedometer reading transformed in a nonlinear way that we'll discover below. Although this postulate sounds a bit technical, here is the physical idea: when we ride in a bus, as we accelerate from the busstop to cruising speed, and as we look out the window, we see the motions of trees and walkers relative to us change continuously and not jerkily.
So now we need to find the matrix $K$. Four more objective, experimentally testable, non relative pieces of physics now enter:


*

*Spatial isotropy: No direction in space has any preference over any other;

*The experimental notion of spatially "Orthogonal" corresponds in the Physical World to the idealized construction, following Euclid's axioms, of the perpendicular bisector of the line joining two points;

*"Movie Reversal": if we reverse the time co-ordinate, we invert co-ordinate transformations. A movie of an object undergoing a change of inertial motion state played backwards shows the same transformation that the object would undergo if the time co-ordinate were reversed (note that this does not generally apply to quantum states of particles, which follow the more general CPT Symmetry, but it does apply, as far as we know, to co-ordinate transformations);

*Our universe is Causal: i.e. the time co-ordinate of a cause is always less than that of its effect: "all causes come before their effects".


Given the spatial isotropy postulate, we can align our co-ordinate system so that the $x$ axis points along the direction relative motion. We then use the orthogonal postulate together with isotropy to conclude that a co-ordinate transformation is unchanged if we rotate the co-ordinate system through any angle about the direction of motion. We actually need the metric notion of orthogonal to define the rotation, and we assume that the Euclidean geometrical notion of rotation, expressed by a rotation matrix conserving the Euclidean inner product, corresponds to the physical notion of rotation. So, if we rotate our co-ordinates about the $x$-axis thus through angle $\phi$, we transform our co-ordinates so that $R_x(\phi)\,\Lambda\,R_x(\phi)^{-1} = \Lambda$ and $R_x(\phi)\,K\,R_x(\phi)^{-1} = K$, thus $K$ must commute with $R_x(\phi)$ and so the invariant subspaces of $R_x(\phi)$ and $K$ must be the same. The eigenvectors of $R_x(\phi)$ are $(0,\,0,\,1,\,\pm i)$ together with any pair of linearly independent superpositions of $\hat{T}=(1,\,0,\,0,\,0)$ and $\hat{X}=(0,\,1,\,0,\,0)$. This assertion together with the understanding that $K$ must be real implies that the most general $K$ matrix must have the form:
$$K=\left(\begin{array}{cccc}\kappa_{t\,t}&\kappa_{t\,x}&0&0\\\kappa_{x\,t}&\kappa_{x\,x}&0&0\\0&0&\kappa_{y\,y}&-\kappa_{y\,z}\\0&0&\kappa_{y\,z}&\kappa_{z\,z}\end{array}\right)$$
Here we assume our co-ordinates are column-vectors of the form $(t,\,x,\,y,\,z)^T$. Now the "Movie Reversal" postulate shows that $K$ must become $-K$ when we reverse the time co-ordinate; thus $K$ anti-commutes with $M=\mathrm{diag}(-1,1,1,1)$. Imposing this anitcommutation, we find:
$$K=\left(\begin{array}{cccc}0&\kappa_{t\,x}&0&0\\\kappa_{x\,t}&0&0&0\\0&0&0&0\\0&0&0&0\end{array}\right)$$
and only the $x$ and $t$ co-ordinates mix by the following $2\times 2$ matrix:
$$\Lambda(\eta) = \exp\left(\eta^\prime\left(\begin{array}{cc}0&\kappa_{t\,x}\\\kappa_{x\,t}&0\end{array}\right)\right) = \left(
\begin{array}{cc}
 \cosh\left(\sqrt{\zeta }\, \eta \right) & \frac{\sqrt{\zeta } }{c} \sinh\left(\sqrt{\zeta} \,\eta \right)\\
 \frac{c}{\sqrt{\zeta }} \sinh\left(\sqrt{\zeta }\, \eta \right)& \cosh\left(\sqrt{\zeta}\, \eta \right) \\
\end{array}
\right)$$
where $\zeta=\pm1$ is the sign of $\kappa_{t\,x}\,\kappa_{x\,t}$ and the constant with dimensions of velocity defined by:
\begin{equation}
\kappa_{t\,x} = \frac{\zeta}{c^2}\,\kappa_{x\,t}
\end{equation}
Since we can absorb any real constant we like into the rapidity parameter and still get an additive rapidity parameter (i.e. $\Lambda(\eta_1)\Lambda(\eta_2) = \Lambda(\eta_1+\eta_2)$), we have replaced $\eta\,\kappa_{x\,t}/c_I$ by $\eta$ in the above.
Lastly, we look at the signature $\zeta$. If $\zeta=-1$, then the matrix above becomes the rotation matrix:
$$\left(\begin{array}{cc}\cos\eta &-\frac{1}{c} \sin\eta\\c \sin\eta& \cos\eta \\\end{array}\right)$$
which means that for every vector between the spacetime co-ordinates of a cause and its effect, we can find an inertial frame, defined by $\eta=\pi$, where this vector is reversed in direction. This clearly violates the causality postulate, so we conclude $\zeta=+1$. When $\zeta=+1$, the transformation is 
$$\left(\begin{array}{cc}\cosh\eta &\frac{1}{c} \sinh\eta\\c \sinh\eta& \cosh\eta \\\end{array}\right)$$
whose eigenvectors are $(t\,x) \propto (1,\,\pm c)$. This means that $c$ is invariant: it is the same constant for all inertial observers. Furthermore, with this choice, we recover our intuitive notion of causality: the everyday observation that causes come before effects but only if we further postulate that the invariant speed $c$ is the speed limit for the propagation of cause-effect, as in my other answer. Causality is not the only physics that would be radically changed if $\zeta=-1$: we know $\zeta=+1$ experimentally without even getting up from our seat:  other physics and relationships that would arise with $\zeta=-1$ are explored by science fiction author Greg Egan in his trilogy Orthogonal[4]. A wonderful and correct summary of some of these weird changes in a non Lorentzian universe are given as a primer for his trilogy on Egan's website[5] and include a variable lightspeed depending on wavelength, thus a spectral spread of colors in the night sky, the {\it decrease} of a body's total energy as its speed increases and the {\it emission} of light by plants to allow them to gain energy by photosynthesis. 
Now, if we set $c\to\infty$ we recover Galileo's Relativity and it is thus seen to be the unique relativity in keeping with our postulates that has absolute time i.e. all inertial observers measure the same time interval between two events. Thus we see that Special Relativity is simply Galileo's relativity with the assumption of absolute time relaxed. When we relax this assumption, Galileo's relativity foretells a whole family of relativites, each parameterized by a different value of $c$. 
So in summary, $c$ doesn't need to be thought of as a speed, but rather simply a universal, nonrelative constant that chooses which of Galileo's relativities is followed by our Universe, and it has the experimental meaning of the maximum speed of propagation of a cause-effect link as I describe in my other answer. To arrive at this conclusion, we have used the nonrelative, objective, experimentally reproducible physical postulates discussed in this answer.
It should be stated that the first person to think along the lines of a relativity not predicated on light was Vladimir Ignatowski in 1910[6]. Other references describing and building on his approach are given in the bibliography of my paper [2], of which a preprint can be seen on my website.

References
[1]: Charles Misner, Kip Thorne & John Wheeler, Gravitation - the famous "big black book", quite a tough project to read, but ultimately very clear and a definitely worthwhile acquisition for anyone interested in either special or general relativity. A hardcover version is also essential (get it second hand: $202 for a paperback is outrageous), as this beast is so large its own weight utterly destroys even the best quality paperback bindings after a few months of fireside reading. You could also wait for a Kindle edition, or, as I did, buy a paperback and have it scanned.
[2]: Rod Vance, "Of Galileo, Groups and What's So Special about the Speed of Light", under review by the  European Journal of Physics 
[3]: Benjamin Crowell, General Relativity See Chapter 2 for an excellent discussion of how the form of the Lorentz transformation follows from affine and metric geometry. Incidentally, he also has a special relativity book
[3b] Benjamin Crowell, Special Relativity but, for fundamentals like we are thinking about here, I actually find the relevant sections of his GR text clearer. He also has a fun read:
[3c] Benjamin Crowell, Relativity for Poets wherein he gives a great presentation of the underlying ideas, philosophies and history of relativity. Although it's meant to be "Relativity Lite" for nonspecialists, nonetheless it does give some clear insights not present in more mathematical treatments, and so is a good read for physicists as well.
[4]: Greg Egan, The Orthogonal Trilogy: book 1 The Clockwork Rocket, (2011) book 2 The Eternal Flame, (2012) both published Nightshade Books; book three The Arrows of Time, (2013) Orion Publishing Group
[5]: Greg Egan, "Plus, Minus: A Gentle Introduction to the Physics of Orthogonal"
[6]: Vladimir Ignatowski, "Einige allgemeine Bemerkungen über das Relativitätsprinzip", Physikalische Zeitschrift 11  pp972–976, 1910 English Translation, "Some General Remarks on the Relativity Principle" is here
A: 
By my reckoning, if all speed is relative, then no mater how fast you
  go light should always race away from you at the same apparent speed.
  I.e. there should be no speed limit.

If an invariant speed $c$ exists, then if an entity has speed $c$ relative to an inertial reference frame (IRF), the entity has speed $c$ relative to all IRFs.
That's what it means for there to be an invariant speed.
Now, if you think about that for a little bit, it follows that an entity with speed less than (or greater than) $c$ in an IRF, cannot have speed $c$ in any IRF.
Thus $c$ is a limiting speed in this sense:  entities either have speed $c$ in all IRFs or an IRF exists in which the entity has a speed that is arbitrarily close to $c$.
For further reading, I recommend this paper, Nothing but Relativity, in which it is shown that, assuming only the principle of relativity, the most general coordinate transformation involves an invariant speed.

We deduce the most general space-time transformation laws consistent
  with the principle of relativity. Thus, our result contains the
  results of both Galilean and Einsteinian relativity. The velocity
  addition law comes as a bi-product of this analysis. We also argue why
  Galilean and Einsteinian versions are the only possible embodiments of
  the principle of relativity.

A: It is an experimental fact that light moves at the same speed in every reference frame, no matter the underlying theory: see the experiment of Michelson and Morley. Every kinematic and dynamical quantity depends on the reference frame except the speed of light, which is the same for every observer.
Besides the experimental result there is something deeper that comes from the principle of action at distance. All the interactions present in the universe do not propagate instantaneously, namely if something happens somewhere it takes a while for an observer located elsewhere to detect its consequences, and this is true as a matter of fact. For example, if you take a small magnet generating a magnetic field and move it from its initial position it will take some time for an observer located far away to detect the change in the magnetic field generated. This said, as a consequence we must assume that there is somehow a velocity according to which the interactions propagate (no matter what its nature is) and also this velocity must be an upper limit for every other event in the universe, otherwise such events will happen before they can actually propagate and this would obstruct the initial assumption that they must propagate first in order to be detected. In other words if there is a speed of "propagation" for action at distance then this speed must be an upper limit; also, it must not depend on the reference frame  either, otherwise it would not be by definition the speed of propagation.
Once you understand that such limit velocity must exist it is easy to introduce it into the equations: you have to nothing but postulate that the same event propagates with that upper velocity limit in any reference frame, namely you end up with
$$
c^2t^2-x^2-y^2-z^2=c^2t'^2-x'^2-y'^2-z'^2
$$
where everything on the right hand side is primed except the upper velocity $c$. This is the starting point of the special theory of relativity.
That this velocity is accidentally the speed of light is proven experimentally. A nice walkthrough is given by Landau & Lifschitz in their textbooks on classical field theory; nevertheless it could be interesting to have a look at the original paper by Einstein as well (although I find it ill-written).
A: It sounds like your confusion is coming from taking paraphrasing such as "everything is relative" too literally. Furthermore, this isn't really accurate. So let me try presenting this a different way:
Nature doesn't care how we label points in space-time. Coordinates do not automatically have some real "physical" meaning. Let's instead focus on what doesn't depend on coordinate systems: these are geometric facts or invariants.  For instance, our space-time is 4 dimensional. There are also things we can calculate, like the invariant length of a path in space-time, or angles between vectors.  It turns out our spacetime has a Lorentzian signature: roughly meaning that one of the dimensions acts differently than the others when calculating the geometric distance.  So there is not complete freedom to make "everything" relative. Some relations are a property of the geometry itself, and are independent of coordinate systems.  I can't find the quote now, but I remember seeing once a quote where Einstein wished in reflection that instead of relativity it was the "theory of invariants" because those are what matter.
Now, it turns out that the Lorentzian signature imposes a structure on spacetime.  In nice Cartesian inertial coordinates with natural units, the geometric length of a straight path between two points is:
$ds^2 = - dt^2 + dx^2 + dy^2 + dz^2$
Unlike space with a Euclidean signature, this separates pairs of points into three different groups:
$> 0$, space like separated
$< 0$, time like separated
$= 0$, "null" separation, or "light like"
No matter what coordinate system you choose, you cannot change these. They are not "relative".  They are fixed by the geometry of spacetime.  This separation (light cones if viewed as a comparison against a single reference point), is the causal structure of space time.  It's what allows us to talk about event A causing B causing C, independently of a coordinate system.
Now, back to your original question, let me note that speed itself is a coordinate system dependent concept.  If you had a bunch of identical rulers and clocks, you could even make a giant grid of rulers and put clocks at every intersection, to try to build up a "physical" version of a coordinate system with spatial differences being directly read off of rulers, and time differences being read from clocks. Even in this idealized situation we cannot yet measure the speed of light. Why? Because we still need to specify one more piece: how remote clocks are synchronized.  It turns out the Einstein convention is to synchronize them using the speed of light as a constant.  So in this sense, it is a choice ... a choice of coordinate system.  There are many coordinate systems in which the speed of light is not constant, or even depends on the direction.
So, is that it? It's a definition?
That is not a very satisfying answer, and not a complete one.  What makes relativity work is the amazing fact that this choice is even possible.
The modern statement of special relativity is usually something like: the laws of physics have Poincare symmetry (Lorentz symmetry + translations + rotations).
It is because of the symmetry of spacetime that we can make an infinite number of inertial coordinate systems that all agree on the speed of light.  It is the structure of spacetime, its symmetry, that makes special relativity.  Einstein discovered this the other way around, postulating that such a set of inertial frames were possible, and derived Lorentz transformations from them to deduce the symmetry of space-time.
So in conclusion:
"If all motion is relative, how does light have a finite speed?"
Not everything is relative in SR, and speed being a coordinate system dependent quantity can have any value you want with appropriate choice of coordinate system.  If we design our coordinate system to describe space isotropically and homogenously and describe time uniformly to get our nice inertial reference frames, the causal structure of spacetime requires the speed of light to be isotropic and finite and the same constant in all of the inertial coordinate systems.
A: 
By my reckoning, if all speed is relative, then no mater how fast you go light should always race away from you at the same apparent speed. 

It does. Thats the clever bit! No matter where you are or how fast you are going, you will always get the same measurement of 3*10^8 meters per second for the speed of light (in vacumn) as every one else. 
Of course, for this to be true, then what you get when you measure a meter or a second must change as your velocity changes. This is what they mean when they say 'time slows down' as you get faster and it also explains why nothing that has mass can reach the speed of light. (Mass means dimension which would have to become infinite for light to still be measured at 'c' relative to the mass and that can't happen). 
A: Although there are several excellent answers, perhaps my answer will remove your confusion.  In your statement "if all motion is relative... finite speed" you need to pay special attention to the words motion and speed.
Motion is just a space displacement.  How fast it is accomplished, is irrelevant.
Speed is a rate of change of space displacement per unit of time. They are different "entities."
An example might make it clearer:
There are two ships in the sea, one is going east at 100 mph, and the other is going west at 100mph.  They are parallel to each other and about 100 ft apart.  A fish swims between them at a speed of 200 mph.
The question now is, what is the speed of the fish? The answer, obviously, is 200 mph.
What is the relative motion of the ships?  They are moving away from each other.
The ships motion has nothing to do with the fish's speed.  This speed is determined by the characteristics of the fish and the sea water.  Likewise, the speed of light (electromagnetic waves), depends on the characteristics of light and the propagation "medium."
Assuming a homogenous universe, the speed of light would have a constant value throughout the universe (independent of any observer).
A: 
If all motion is relative, how does light have a finite speed?

Because of the wave nature of matter. Check out the The Other Meaning of Special Relativity by Robert Close. When you and your rods and clocks are all made out of waves, you calibrate your rods and clocks using the motion of waves, then use them to measure the motion of waves. It doesn't matter how fast those waves move, this inherent tautology means you always measure the speed of light to be the same. See http://arxiv.org/abs/0705.4507 where Magueijo and Moffat talk about it: 
"Following Ellis, let us first consider c as the speed of the photon. Can c vary? Could such a variation be measured? As correctly pointed out by Ellis, within the current protocol for measuring time and space the answer is no. The unit of time is defined by an oscillating system or the frequency of an atomic transition, and the unit of space is defined in terms of the distance travelled by light in the unit of time. We therefore have a situation akin to saying that the speed of light is “one light-year per year”, i.e. its constancy has become a tautology or a definition." 

I've often heard that Einstein shattered the notion of absolute motion (i.e. all things move relative to one another) and that he established the speed of light as being absolute. That sounds paradoxical to me; I cannot understand how the two concepts can be reconciled.

It's a myth popularized by people who've never actually read what Einstein said, and who appeal to his authority whilst flatly contradicting what he said. See this:

The speed of light varies in the room you're in. If it didn't. your pencil wouldn't fall down. Also see this Baez article.

Back to the question: Relativity shows us that there is no universal frame of reference by which to judge motion.

That's another myth I'm afraid. Check out the CMB rest frame. Our local group of galaxies is moving at circa 627 km/s relative to the reference frame of the CMB.   

Then there's the speed of light (in a vacuum). The speed of light is the ultimate "speed limit," it's often said. But if there is no universal frame of reference, how can there be any such speed? The very idea only make sense if there is a universal frame.

See above. The CMB rest frame is the reference frame of the universe. 

All these spacetime bending consequences used to explain why nothing can move past this speed only seems to enshrine the concept that there is some ultimate speed standard.

Check out pair production and the wave nature of matter. Nothing can move faster than the speed of waves because they're made of waves.   

Perhaps that there is an actual fabric of space which everything moves relative to, which is why there is something to expand between galaxies (faster than light can propagate) in the metric expansion of space. Growing up, I always thought this would just start makes sense with time. Now I'm up to a first year (college) level in physics, I even know basic calculus, yet I'm still hopelessly confused.

Read what Einstein said, and you won't be. He thought of space as a something rather than a nothing, see his 1920 Leyden Address. And read this by Nobel Laureate Robert B Laughlin:   
"It is ironic that Einstein's most creative work, the general theory of relativity, should boil down to conceptualizing space as a medium when his original premise [in special relativity] was that no such medium existed..." 
A: For starters, Special Relativity only seems bizarre to someone who does not see it at work in its entirety.  If its entirety is being seen, it becomes nothing but a simple single image. From that simple single image one can, in mere minutes, derive the entire collection of Special Relativity equations. To learn of Special Relativity by one's self, you simply need to analyze motion by one's self, and do so by starting from scratch.
Imagine the existence of an "Absolute" 4 dimensional environment that has 3 dimensions of space, and 1 dimension of time. Let's call it Space-Time. Now imagine that all objects that are located within this 4D environment, are constantly on the move, and that they are all moving with the same magnitude of motion. 
If this motion was in the direction of moving across space only, this ongoing motion would be measured by others as being the speed of light. Thus overall what we have is "Absolute" motion that is constantly ongoing within an "Absolute" 4D environment. If a bird changes its direction of spatial travel, the bird rotates in space. If any object within 4D Space-Time changes its direction of travel, it too will rotate. 
Now, if you proceed to analyze the outcome that is produced via this combination of "Absolutes" and rotation, you end up with Special Relativity, and you also quickly derive all of the mathematical equations.  
By starting with the absolutes which lead you to Special Relativity, one in turn sees the absolute foundation of which Special Relativity resides within. Once this is achieved, it becomes child's play to understand why all observers measure the speed of light as being 300,000 km/s.
However, if these absolutes are left out of the picture, then ones understanding of Special Relativity becomes less than absolute, thus the speed of light in turn has no absolute reference.
A: The general principle of relativity  


*

*Local laws of physics are the same irrespective of the reference matter which a particular observer uses to quantify them


is an expression of Hume's Principle of uniformity in Nature, 


*

*the fundamental behaviour of matter is always and everywhere the same.


Without this principle, there would be no science because if laws could change observing them would be meaningless.
It follows that all observers can set up coordinate systems in exactly the same way. There are then two possibilities. Either there is, or there is not, a maximum speed in nature. If there were not, the laws of physics would be different from those we observe (e.g. Newtonian relativity would hold for classical electrodynamics and numerous empirically confirmed predictions of relativity would have been false. Maxwell's equations and Newtonian mechanics are not empirically compatible. Observation supports Maxwell's equations, and relativity shows how to modify Newtonian mechanics to match observation.). Hence there is a maximum speed which is necessarily constant for all observers.  
Relativity depends on this logical argument, not strictly on the physical speed of light. It just happens that, to the accuracy of measurement, the speed of light is equal to the maximum speed.
A: How does light have a finite speed?
The speed of light, which is 1 lightsecond per second (denoted at C = 1ls/s). Is a constant and invariant speed limit. And it is so, so that causality in the framework of Einstein's relativity can be preserved.
The way that this is done, is by axiomatically accepting that our theory is going to talk about a Universe that has a spacetime, and in that spacetime, EVERYTHING (at least macroscopically) can travel at ONE and ONLY ONE speed! The speed of C = 1ls/s.
That axiom or postulate, is given to our theory by us, because that's the kind of Universe that we want to examine! We want to examine, "how would such a Universe behave if it had a speed limit" because that's what our experiment showed... So that's the kind of Universe we want to examine...
Whether or not our theory is going to be usefull for the real world, for now is irrelevant...

So in that theoretical Universe that we just defined, you can travel ONLY at C in spacetime... Which means that you can go as fast in space as you want, or as fast in time as you want AS LONG AS, your net speed in spacetime is ALWAYS equal to C.

So everything is traveling at the speed of light in that spacetime! Even you and me right now! The only diffrence is, that we are traveling very slow in space but also very fast in time... If you combine both speeds (speed in time and speed in space), you are traveling at exactly the speed of light in spacetime!
If you now start going close to the speed of light in space, you will be going very fast in space but also very slow in time... At the end your speed in spacetime will still be equal to C...
For light now, its going as fast as it can in space and in time its speed is going to be ZERO! *
And every observer can of course consider him/her self as stationary in space . (Which will mean that they are aging at the speed of light in time (from their perspective)). And if that spacetime is flat, they will be right!

Another popular question to this is "why can't I go faster than light?"
Well you can! Sort of! :D
You see, before Einstein we thought that you can reach any speed in space as you wanted... Which means that you could theoretically travel 1 lightyear per day if you wanted to...
But lets see what that means...
If you start at the date 01/01/2000 and travel 1 lightyear per day towards a 1 lightyear away star... It will mean that when you arrive to your destination, the time there will be 02/01/2000... Because it took you 1 day to get there!
Now with Einstein that's still true! You can still travel at 1 lightyear per day! But there is a problem!
So you get into your spaceship, you travel at the speed of 1 lightyear per day, and you arrive to that 1 lightyear away star after one day... So for you the date is 02/01/2000. But when you take a look at the date there, it reads 01/01/2050
:O
From your point of view, 1 day passed... But from their point of view, 50 years passed! (Numbers are random just for the example...)
So you realise, that you can still travel at any speed you want, but time will not follow you! Because the faster you travel in space the slower you travel in time! So at the end, IN SPACETIME, you still traveled at bellow lightspeed speed! Even though you reached a lightyear away star in 1 day, your net speed in spacetime was still slower than the speed of light!
:O
Light, can reach ANY distance INSTANTLY from its own perspective... Because light's speed in time (as we said *) is zero! But from our point of view, light still takes 8 minutes to get here from the Sun...
So as you can see, you CAN travel as fast as you want, and reach any distance in any time... AS LONG AS, you only care about YOUR TIME! Because when you arrive to your destination, the people that potentially lived there, will have been long gone, aged and died...
That's the meaning of the Universal speed limit!
Ultimately the speed limit is because we discovered that spacetime is hyperbolic. An Euclidean spacetime has a speed limit in time. A hyperbolic spacetime has a speed limit in spacetime.
