If we could fly away from the Earth (imagine Superman), at what point would we notice the Earth's spin (or at what point would be stop moving along with the Earth)? Or is that just not how relativity works, if not please do explain how.
It isn't a question of distance from the Earth. It is just a question of relative velocity. For example if you were next to a geostationary satellite in a geostationary orbit then you would not observe the rotation of the Earth; the Earth would still appear to be stationary to you.
On the flip side, if you were to (somehow) hover $1\,\rm m$ above the surface of the Earth and then (somehow) change your velocity relative to the Earth, then you would see the Earth's surface move relative to you.
Therefore, the distance from the Earth is irrelevant. You could technically rotate with the Earth at any distance from the Earth as long as the correct force(s) is(are) being applied to you. In the same way the distance from the Earth doesn't determine if you are able to move relative to it.
Suppose a rocket always flying in a vertical position at the equator region, and its engine can't move it sideways. In the first kilometers the air density is enough to keep it in the same frame of the base, or rotating with the earth.
But after 100 km, that is conventionally taken as the thickness of the atmosphere, there is no more air drag. So its velocity vector is the sum of a radial component due to the engine and another one constant and normal to the radial component (consequence of the initial frame). $\mathbf v = \mathbf v_r + \mathbf v_n$
As $\mathbf v_n$ doesn't change its direction while the earth rotates, an imaginary line from the centre of the earth to the rocket will gradually cross the earth surface at a point more to west. What translates to an observer in the rocket as a rotating earth.