What is the exact relation between anti-matter and relativity? I have seen in relativistic QM that, when trying to create the Dirac Equation, it only make sense to be acting on -- at minimum -- a 4-component vector (actually a bi-spinor).  I guess this is because the smallest representation of the Clifford algebra is 4-dimensional? 
Then the components get identified as antiparticles.  But this seemed very much like an accident, or coincidence.  Is it?  Or is there a good reason that antiparticles turn up specifically when I try to make a relativistic QM? I never saw anything very relativity-y about antiparticles before now; they're just other particles.
My best guess for the connection is that one requires anti-particle modes in their fields to be relativistically invariant; maybe different observers see different amounts of particle/antiparticles?  Then this is just the dirac equation preempting QFT.  I do not know.
 A: To understand the relation better, it is best to trace back the history of discoveries as they were made in the early days of quantum field theory.
Let's start with Schrodinger's equation:
$$ i\hbar \frac{\partial}{\partial t} \Psi(t, {\bf x}) = - \frac{\hbar^2}{2m} \Delta \Psi(t, {\bf x}). $$
It describes a quantum Newtonian particle. The standard terminology is to use the word "classical" for "not quantum", and "Newtonian" for "not relativistic".
Schrodinger's equation in the vacuum can be easily solved. Its solutions are plane waves
$$ \Psi_{\bf k}(t, {\bf x}) = e^{-i E({\bf k}) t + i {\bf k} {\bf x}}, $$
where $E({\bf k}) = {\bf k}^2 / 2m$ is the Newtonian formula for the energy of the particle. The wave isn't normalizable, which signals that real physical states are superpositions of waves subjects to extra constraints (the relevant subspace of $L_2(\mathbb{R}^3)$ is called the Sobolev space, it consists of exponentially decaying at spatial infinity wavefunctions).
Nevertheless, there's a straightforward physical interpretation of a single wave $\Psi_{\bf k}$ – it is an eigenstate of the momentum operator with eigenvalue ${\bf k}$. So it describes a particle of positive energy $E$ and momentum ${\bf k}$. So far so good.
But Schrodinger's equation, despite being a huge success, has a major conceptual problem with it – it isn't relativistic.
Now there's a relativistic wave equation called the Klein-Gordon equation:
$$ \frac{\partial^2}{c^2\,\partial t^2} \Psi(t, {\bf x}) - \Delta \Psi(t, {\bf x}) + m^2 \Psi(t, {\bf x}) = 0. $$
To see that this equation is relativistic is straightforward – you simply rewrite it as
$$ \left( \partial_{\mu} \partial^{\mu} + m^2 \right) \Psi = 0, $$
which is manifestly Lorentz-invariant.
How do we make sense of its solutions? What are the solutions?
Well, an obvious strategy would be to plug in the plane wave $\Psi_{{\bf k}, E}$. You will find that it is indeed a solution of the Klein-Gordon equation, if
$$ E({\bf k}) = \pm c \sqrt{{\bf k}^2 + m^2 c^2}, $$
the expression in which you could easily spot Einstein's very own formula for the relativistic dependency of energy on momentum.
We therefore have a nice limit $c \rightarrow \infty$ in which Special Relativity becomes Newtonian physics. Of course what actually happens is $k \ll m c$, which justifies setting $c$ to $\infty$ as it is much larger than the typical scale of the dimension $m/s$ which is $k/m$.
But now this limit, which we were already aware of from the introductory course on Special Relativity, shows up in the quantum theory. E.g. this is now a limit of waves:
$$ e^{-ic\sqrt{{\bf k}^2 + m^2 c^2} + i {\bf k} {\bf x}} \rightarrow e^{-i m c^2 t} e^{-i c t {\bf k}^2 / 2m + i {\bf k} {\bf x}}.$$
This is great – we have a nonrelativistic limit in the quantum theory, so Klein-Gordon equation can be regarded as the most deep and fundamental description of a particle (because it is both quantum and relativistic), but... We completely ignored the other class of solutions – the ones with $E$ negative (remember the weird $\pm$ sign in front of the square root?).
Negative-energy solutions have no Newtonian counterparts. We simply didn't encounter those when we analyzed Schrodinger's equation! At the same time, they are ubiquitous in Special Relativity – their existence can be traced back to one of the most renowned kinematic identities holding all of the modern physics together – the Einstein's formula
$$ E^2 - {\bf k}^2 c^2 = m^2 c^4. $$
Indeed, that formula is quadratic in $E$, and thus if $E_0$ is a solution, then so is $-E_0$.
How to interpret those solutions? What does it mean for a particle to have negative energy, and why wasn't this observed in experiments?
Dirac was considering a different kind of wave equation, the one which describes a particle with spin $1/2$. It is mostly analogous to Klein-Gordon: a Newtonian version for spin $1/2$ also exists (called the Pauli equation) and Dirac equation admits positive and negative energy solutions, of which positive energy ones have a nice interpretation in terms of solutions to the Pauli equation in the Newtonian limit, and negative solutions don't. So the problem is essentially the same.
But there's one important distinction – Dirac's particles are fermions, i.e. they obey the Fermi-Dirac statistics, and therefore the Pauli exclusion principle. This can only be understood in a multi-particle theory, on the level of a single-particle theory exchange statistics doesn't exist.
This lead Dirac to hypothesize that negative-energy states are already filled perfectly in what we call the vacuum (the resulting object is called the Dirac sea). That was, at the time, the only good solution to the existence of negative-energy states. But existence of the sea means that just as positive-energy states, which aren't filled in the vacuum, can be filled (which we interpret as individual electrons), the negative-energy states that are filled in the vacuum, can be vacated. The resulting "hole" would behave exactly like an electron, except that all its quantum numbers would be reversed (because it is actually a hole, i.e. the absense of an expected electron). This includes its energy and electromagnetic charge. But because this is a negative-energy state, the hole would actually behave as a particle of positive energy and charge – a positron.
It is surprising by how little the picture has changed since then. If you look at the modern formulation of the relativistic QFT of electrons, its Fock space would have exactly the same structure as Dirac's sea. This Fock space is spawned by an algebra of Fermi-quantized creation/annihilation operators for electrons and positrons. One of the properties of Fermi quantization is that the empty and filled states are on the equal footing, which means that matter and anti-matter are on the equal footing in the QFT.
The situation is a little different with the original problem – the one with Klein-Gordon equation. It describes spin-0 particles which are bosons, so Pauli exclusion principle isn't there at our disposal, and the Dirac sea construction doesn't work.
Rather strikingly, it appears that the QFT solution still works. The bosonic Fock space is generated by Bose-quantized creation/annihilation operators for particles and anti-particles.
Finally, how can we make sure that the resulting theory doesn't have negative-energy particles? We look at the Hamiltonian of the QFT itself, not the Hamiltonian of the individual particle:
$$ H = \sum_{\bf k} \left( E_{\bf k} a_{\bf k}^{\dagger} a_{\bf k} + E_{\bf k} b_{\bf k}^{\dagger} b_{\bf k} \pm \frac{1}{2} \right) $$
where $a$ and $b$ are the annihilation operators for particles and anti-particles respectively, and $\pm$ corresponds to bosonic/fermionic case respectively (for the Dirac field, a sum over spin indices is understood). It is easy to show that the vacuum state $\left| 0 \right>$ of the QFT (defined as the state annihilated by all $a$ and $b$) is the lowest-energy state, meaning that $H$ is bounded by below.
Therefore, there aren't any negative-energy states in the QFT. Instead, there's anti-particles. Anti-particles are the multi-particle manifestations of the existence of negative-energy solutions, which are ubiquitous in Special Relativity.
Hope this answers your question.
