Suppose you are floating in space in your rocket and you see another rocket drifting by. Which rocket is still and which is moving? Either point of view is equally correct.
You choose a frame of reference and define motion with respect to it. A frame of reference is a coordinate system. You choose a point as the origin. Often you choose yourself. You choose directions for x, y, and z axes. You can then measure the distance along those directions to any other object. If you keep getting the same coordinates, the object isn't moving.
Generally you choose coordinates so that an object at rest stays at rest unless forces act on it. For example, you choose your rocket as the origin if the engine is off. This kind of reference frame is called inertial. Without forces, objects move at a constant velocity.
If you choose yourself as the origin, and decide the other rocket is moving, you can check the laws of physics. For example, the position of the other rocket is given by
$$\vec x = \vec x_0 + \vec vt$$
Your own position is given by the same equation, but of course $\vec x_0 = \vec 0$, and $\vec v = \vec 0$. You would find all the laws of physics work.
You can make the choice that the origin follows the other rocket, and you are moving. The laws of physics still work.
For your questions about featureless ice, ice isn't featureless. It is made of atoms. You can measure the velocity of atoms. You can treat them as the other rocket.
Gravity makes a difference, in one of two ways.
For everyday situations, you can use classical physics and describe gravity as a force. Often we deal mostly with horizontal movement. Gravity pulls us down and the ground holds us up. The two forces cancel. We can ignore them, and treat the world as an inertial frame of reference.
Or we can do physics with freely falling bodies, whose position is given by
$$\vec x = \vec x_0 + \vec vt + \frac{1}{2}\vec g t^2$$
If you take a deeper look at gravity, things change. General relativity is fundamentally a theory of gravity. It is based on the idea that you can choose any frame of reference, inertial or not. You can find ways to describe all the laws of physics that hold in any frame of reference. The consequences of this are complex and beyond the scope of this answer.