What does "all stop" mean in reality? In science fiction, when a starship captain commands "all stop," the audience simply assumes that, like a terrestrial naval ship anchored to the ocean floor, the ship literally comes to a complete stop.

Does our current understanding of celestial mechanics provide a meaningful definition of a complete stop in space &mdash; for any object?
As mentioned in the comments, in relativity, "all stop" can only be in reference to some other object, or set of objects.  Still, I would argue there remains some interesting potential for the "all stop" concept in physics theory, because Einstein was motivated by Mach's principle when creating general relativity (regardless of whatever version of that principle is formally supported in that theory), and so we might suspect that "all stop" can have the theoretical local meaning of "at rest with respect to the center of mass of everything around it that is affecting it."  

That notion is trickier in an expanding universe, where the concept of a center of mass gets replaced with the concept of "at rest with respect to the cosmic microwave background", which is normally treated as a kind of accident of history, rather than a theoretical truth.  Still, since the Big Bang model is often taken as asserting that the accidental history of our universe is actually relevant to the origin of our universe and its theoretical properties, as well as to the origin of the laws that our universe obeys, it is not a great stretch to imagine that an "accident of history" kind of preferred frame could still, nevertheless, have a formal status in the laws as a kind of true "all stop" frame-- albeit only locally.