Do curved spaces always have a preferred rest frame? A distinguishing feature of globally curved spaces is that parallel lines don't remain equidistant--in a positively-curved space, they converge, and in a negatively-curved space, they diverge.
If the parallel lines under consideration are the velocity vectors of different particles in an extended object, that would seem to imply that a moving object in a curved space will experience a compressive or explosive pseudoforce perpendicular to its direction of motion, and proportional to its speed. Different bits of the same object will have to continually accelerate to maintain their separation. Which in turn suggests a simple experiment to determine the rest frame of space--it's the frame in which that force is zero.
Is there some error in my reasoning, or is it in fact the case that a non-Euclidean universe always has an obvious preferred rest frame?
 A: The main error in reasoning is in forgetting that general relativity deals with curved spacetime while OP's intuition is about curved space, disregarding the time component. Separation between two nearby timelike geodesics is given by geodesic deviation equation. And in most spacetimes of physical interest time components of curvature tensor appearing in the equation are important. For example, in the weak field limit of GR, where Newtonian gravity applies, this separation is approximately:
$$
\frac{d^2 X^i}{dt^2}\approx - R^{i}_{0j0}X^j\approx \frac{\partial^2 \Phi}{\partial X^i \partial X^j} X^j,
$$
where $\Phi$ is the Newtonian gravitational potential. While the contribution from purely spatial parts of curvature tensor would be small post-Newtonian corrections that could be ignored in many cases.
There is a class of spacetimes where the OP's argument almost works: so-called ultrastatic spacetimes, where there is a timelike Killing vector field $\xi$ with a constant norm $\xi_\mu \xi^\mu=-1$ and where there is a hypersurface $\Sigma$ orthogonal to $\xi$. This Killing vector field defines a reference frame (generally unique for a given spacetime, so it would indeed be a preferred frame) such that static observers are inertial and thus there would be no acceleration needed to maintain constant separation.
The wording “almost works” and “generally unique” is connected to another misconception on OP's part, that curvature would be either positive or negative. But, if the dimension is greater than $2$, curvature must be characterized by a tensor, so e.g. parallel lines can diverge along one direction and can converge in another. This also means that in a curved space it is possible to have directions displacements along which would not generate accelerations for equidistant observers, and so even in the ultrastatic spacetimes the preferred rest frame may not be unique. Consider e.g. a direct product $\mathrm{M}^{1,1}\times S^2$ of two dimensional Minkwoski spacetime  and a sphere: instead of a single timelike KVF it has infinite number of them related by Minkowski boosts.
A: A counter example is a spacetime with a gravitational wave passing through otherwise empty space. While there are so-called "transverse-tracless" coordinates where freely falling observers remain at the same coordinate values in such a spacetime, the physical distances between observers will change as a gravitational wave passes by, unless they accelerate to maintain their separation.
A: 
Different bits of the same object will have to continually accelerate to maintain their separation. Which in turn suggests a simple experiment to determine the rest frame of space — it's the frame in which that force is zero.

You are confusing coordinate and proper acceleration. The intermolecular forces that are responsible for maintaining the shape of an extended body are real forces, and real forces result in proper acceleration which can't be transformed to zero by changing reference frames.
For example, a person standing on Earth will naturally attempt to move radially inward, but the (electromagnetic) normal force from the surface of the Earth resists it. As a result, the person feels a real force upwards.
