The Hole Argument I have read explanations of this but haven't really understood. Given a spacetime $(M,g)$ I have read that if I represent the metric in some coordinates $(x,y,z,t)$ as $g(x,y,z,t)$ and then in another coordinate system as $g'(x',y',z',t'),$ that $g'(x,y,z,t)$ (now using the old coordinates) will also solve the Einstein equations. Now $g$ and $g'$ are two different metrics on the manifold and so should predict different physics, but somehow they are the same? If I measure the distance between two points on the manifold I should get different answers if the metrics are different, shouldn't I? This is the part I don't really understand. Is it something like $(M,g')$ isn't a solution, but only $(M',g')$ where $M'$ is diffeomorphic to $M$?
To give an explicit example, let's look at the Schwarzschild metric: \begin{equation}
 ds^2=-\left(1-\frac{2GM}{c^2 r}\right)c^2dt^2+\left(1-\frac{2GM}{c^2 r}\right)^{-1}dr^2+r^2\left(d \theta^2 +\sin^2 \theta d \phi^2\right) \;.
\end{equation} Apparently (according to http://faculty.luther.edu/~macdonal/HoleArgument.pdf) \begin{equation}
 ds^2=-\left(1-\frac{2GM}{c^2 f(r)}\right)c^2dt^2+\left(1-\frac{2GM}{c^2 f(r)}\right)^{-1}f'(r)^2dr^2+f(r)^2\left(d \theta^2 +\sin^2 \theta d \phi^2\right) \;
\end{equation}
is also a solution for any diffeomorphism $f$ though distances aren't the same. Of course when deriving the Schwarzschild metric it seems (according to Carroll's book) $(r,\theta,\phi,t)$ are just symbols that you only interpret after you find the metric, which is confusing. Note I didn't do a change of coordinates here, I changed the actual metric. Are they really both solutions on the same manifold?
 A: Changing the coordinates of a metric does not change the underlying physics, nor the solution. A metric $g$ describing a manifold $M$, if under diffeomorphisms is transformed to a new metric $g'$ it will still describe the original $M$.
A: When you change coordinates, you just choose a different atlas for $\mathcal{M}$. This does not change the metric $g$, as it is defined independent of coordinates.
Now, your Schwarzschild example has little to do with this, since there you are talking about a diffeomorphism $t : \mathcal{M} \rightarrow \mathcal{M'}$. Yet, if $\mathcal{M'}$ is not already endowed with a metric, your natural choice for a metric $g'$ on it is
$$ g'(\mathrm{d}t(X),\mathrm{d}t(Y)) := g(X,Y) $$
which means requiring that $t$ is an isometry.
So, when you choose $t$ to be an automorphism of $\mathcal{M}$, and only act upon the coordinate $r$ as a smooth $f(r)$, the induced metric on the target manifold (which is $\mathcal{M}$ itself) is exactly the second metric you wrote down if the source manifold is endowed with the usual Schwarzschild metric. As these two are isometric, they describe the same physics. In particular, it implies that $g'$ is also a solution to the Einstein equations. Thus, both $(\mathcal{M},g)$ and $(\mathcal{M},g')$ are allowed spacetimes.
So, I just skimmed the paper, and, as it turns they really just do a coordinate change: They change the radial coordinate as $f(r') = r$. So, you've the metric given w.r.t. $(t,r,\phi,\theta)$ by your first equation, and you've the metric given w.r.t. $(t,r',\phi,\theta)$ by your second equation. They're the same, since, for any point $p$, the coordinates are related as $f(r') = r$. They are not two different metrics, just different coordinate expression.
A: 
Now g and g′ are two different metrics on the manifold and so should
  predict different physics, but somehow they are the same?

The field equations require four coordinate conditions for a unique solution.
For the Schwarzschild line element, a coordinate condition is that the surface area of each sphere is $4\pi r^2$.
For the line element of the 2nd solution you provide, a different coordinate condition is used; the surface area of each sphere is $4\pi f^2(r)$ so this line element belongs to a different spacetime manifold but one that is a static solution for a vacuum spherically symmetric spacetime.
From the linked paper:

General relativity considers $G$ and $G'$ to live on different
  spacetime manifolds, say $M$ and $N$. To distinguish them, rename
  their $r$ coordinates to $r_M$ and $r_N$.
Map an event $E_N \in N$ at $r_N$ to the event $E_M \in M$ with $r_M =
 f (r_N)$, with the other coordinates unchanged. Then the
  transformation maps $G'$ to $G$.

