> everything moves through spacetime at c

No. Everything has its own worldline through spacetime, and between two events at point p and q on a worldline through a given spacetime we can measure the interval dS between p and q. When we normalize the interval against a set of coordinates and a chosen metric signature (here +++-) we can have three types of interval: dS^2 = 0 is lightlike, dS^2 > 0 is spacetlike and dS^2 < 0 is timelike.

A concrete example using the Minkowski metric for a set of Cartesian coordinates dS^2 = dx^2 + dy^2 + dz^2 - cdt^2. If we have a test object that always remains at the (x=0,y=0,z=0) origin of the coordinates then as the "t" coordinate increases with the passage of time, -cdt^2 is the only nonzero component of dS^2. From t=0 to t=10000 (where t is in, say, seconds) is perfectly timelike interval. However, any way we vary x, y, and z, (measuring the coordinate distances in, say, light-seconds) if the changes are small compared to the constant factor c, we will have a timelike interval. Light itself, conversely, follows a lightlike interval. If we restrict a beam of light to move only on the x axis, then we have (in (light-)seconds and seconds) x=c, t=1; x=2c, t=2; x=3c, t=3; and so forth; the -c factor cancels out the change in x at each step, so dS^2 = 0.

But bear in mind here that the Minkowski metric is just one of many known exact solutions to the Einstein Field Equations, and there are many many many known approximate solutions. Moreover, we are free to use arbitrary coordinates. The Minkowski metric looks different in spherical polar coordinates, for example. We are also free to use arbitrary units. We can even use the metric signature (-,-,-,+) if we like. However, when we take all of these into account, we're left with the same distinction based on the interval: they're either lightlike, timelike, or spacelike.

A lightlike worldline is one in which intervals on the worldline are always light-like; a timelike worldine is one in which intervals on the worldline are always spacelike.

We have strong evidence and stronger theoretical reasoning to expect that massless objects will always have lightlike worldlines (and that light itself is massless) while massive objects will always have timelike worldlines.

So:

> Electromagnetic waves have no mass, they don't travel in time, so the entire portion of their travel takes place in space

No, they have lightlike worldlines. An interval between any two points on the wave's worldline will be lightlike. This generally means that changes in the spacelike coordinates will exactly match the change in the timelike coordinate multiplied by the constant factor c. However, under most reasonable choices of coordinates, the "t" coordinate will certainly vary from point to point along its worldline.

However, one has free choice to decide which axis is timelike or spacelike, and different choices may seem like the natural ones to different observers.

In order to cope with these sets of choices we write down the laws of physics in a generally covariant manner. This has been one of the greatest successes of relativity; any proposed theory that cannot be written down in generally covariant form is almost certainly unphysical in some way.

Lastly, the value of "c" is determined empirically, and will vary depending on one's choice of units. Relativists will often use a system of units in which c is set to unity (c=1), for example, in order to simplify the form of equations.

> (GPS satellites do have to account for this)

The theory side of GPS relies upon covariance matrices.