Gauge transforms, gravitational waves, and the speed of thought The relation between Gauge theories and physical constants can be summed up as follows [1, verbatim]: 

In gauge theories, the physical content is gauge invarient: the physical properties of a configuration do not change under a gauge transformation...

Gravitational waves are physical entities which can be measured both indirectly (e.g. the Hulse and Taylor binary pulsar [2]) and recently directly (i.e. LIGO).  
Let the presence of (linearized) physical gravitational waves depends on the Gauge chosen - you need to use the harmonic gauge else you simply get waves that travel at the speed of thought. Eddington had similar arguments in is 1923 book [3].
I am confused, therefore about the application of gauges here. Our choice of gauge changes the physics. You can choose one gauge and get gravitational waves traveling at the speed of light, but choose another and you don't [3] i.e. our gauge conditions don't seem like gauge conditions, but cause actual physical difference between solutions. Please can someone explain the resolution and how it is applicable to think of this situation.
References
[1] Hemker, P.W. and Wesseling, P. eds., 2012. Multigrid Methods IV: Proceedings of the Fourth European Multigrid Conference, Amsterdam, July 6–9, 1993 (Vol. 116). Birkhäuser. (p63)
[2] Weisberg, J.M. and Taylor, J.H., 2005, July. The
relativistic binary pulsar b1913+ 16: Thirty years
of observations and analysis.
 In
 Binary Radio
Pulsars
 (Vol. 328, p. 25).
[3] Eddington, A.S., 1930. Mathematical theory of relativity. General Books LLC.
 A: In this answer we are working in the linearized theory. Thus unless otherwise stated everything only holds to first order. Although I asked the question I have written the question in the style I would answer a question I had not asked (i.e. use of 'you' etc)
The Meaning of a Gauge Transform in GR
Consider the two metrics: 
$$ g_{\mu \nu}=\eta_{\mu \nu}+h_{\mu \nu}$$
$$g'_{\mu \nu}=\eta+h_{\mu \nu}-\partial_\mu \xi_\nu-\partial_\nu \xi_\mu$$
where $\xi_\nu$ is an arbitary but small covector. It turns out that $g_{\mu \nu}$ and $g'_{\mu \nu}$ in the same coordinates have the same Riemann tensor and therefore satisfy the same Einstein equations. This means they correspond to the same stress-energy tensor and therefore the same physical solution. Thus by making the transformation: 
$$h_{\mu \nu}\rightarrow h_{\mu \nu}-\partial_\mu \xi_\nu-\partial_\nu \xi_\mu$$
$$x_\mu \rightarrow x_\mu$$
we leave this physical situation unchanged. Such a transformation, in this context is called a gauge transformation.
The Speed of Thought
You said:

Let the presence of (linearized) physical gravitational waves depends on the Gauge chosen - you need to use the harmonic gauge else you simply get waves that travel at the speed of thought.

This statement is not as general as you make out which can be proved by a simple argument:

Let $h_{\mu \nu}$ correspond to a physical gravitational wave (i.e. produces curvature) in the harmonic gauge then (to first order): 
$$h'_{\mu \nu}=h_{\mu \nu}-\partial_\mu \xi_\nu-\partial_\nu \xi_\mu$$
must also produce a physical gravitational wave but in general is not in the harmonic gauge. 

Where your comment does apply is in the case of plane waves, as described here. If we take a solution of the form: 
$$h_{\mu \nu} =A_{\mu \nu} e^{ik_\rho x^\rho}$$
for some constant tensor $A_{\mu \nu}$. This only corresponds corresponds to a physical wave traveling at the speed of light if $h_{\mu \nu}$ is in the harmonic gauge, else it corresponds to a coordinate wave traveling at the 'speed of thought' (i.e. not the speed of light, and not a real wave). However, the metric with:
$$h'_{\mu \nu}=A_{\mu \nu} e^{ik_\rho x^\rho}-\partial_\mu \xi_\nu-\partial_\nu \xi_\mu$$
corresponds to the same physical wave and is not in the harmonic gauge - we just can't write it as a plane wave. 

Concluding Remarks
The crux of your question lays in the statement:

You can choose one gauge and get gravitational waves traveling at the speed of light, but choose another and you don't [3] i.e. our gauge conditions don't seem like gauge conditions, but cause actual physical difference between solutions. 

I hope I have convinced you that this statement is false. By changing gauge you change the form of the solution (i.e. from a nice plane wave to something nasty) but do not, and cannot change the physical content. 
