Disclaimer: I may work on software that has to automatically shift between a dozen frames and coordinate systems on a constant basis to meet user needs and expectations!
I think you might be putting too much into GPS =) I'm going to divide this into two parts. First part is an ephemeris overview, the second is more directly associated with the question.
I think you're actually trying to do several things at once:
- GPS is a way to measure time signals and map them back into space to define a point in space.
- ECEF is a coordinate system (Earth Centered, Earth Fixed) where points on the surface of the idealized Earth don't move. ECI (Earth Centered, Inertial) is an inertial coordinate frame. Points on the surface of the earth move fast in this coordinate system, but the coordinate system is not rotating (more on that later)
- Instructions need to be able to describe where to go.
Each of these is a separate issue. As an example, the output of GPS is a point in space, but it isn't necessarily in any particular coordinate system. You can always convert from one system to another without losses. For example, it is really common to use ECEF to map GPS points onto the earth, because for most common purposes, we'd like "stationary" objects to not move. This can also be converted into latitude/longitude/alt (LLA), which is what people typically think of for "GPS coordinates," using nothing but basic trigonometry.
However, there are situations where this system does not give good results. Consider if your target is moving (such as planets always are). It is not meaningful to give out the "GPS coordinate" of a moving car, because the car rapidly leaves that location. Likewise, the XYZ coordinates of a planet will likely shift over the years, unless your coordinate system is fixed to the planet.
There are also situations where you don't want ECEF or LLA. ECEF is a "rotating" frame because the Earth is rotating, and it is tied to the earth's surface movement. Because it is rotating, you have centripetal acceleration and the Coriolis effect. This means, for objects propagating over long times (like planets would in your example), their motion is actually a remarkably complicated shape. Modern sniper computers actually have to account for the Coriolis effect, making the bullet twist to the side in a non-intuitive manner! For positioning satellites, people talk almost exclusively in ECI. ECI is an inertial frame, so Netwon's laws of motion work roughly like you expect them to (at the price of points on the surface of the earth having large apparent veloicites.
The first major challenge of your problem is defining a coordinate system, so lets look at how we do it today.
An intuitive guess would be that we start with ECEF, and build outwards to LLA and ECI. However, this is not the way they are defined. A coordinate system must have a mathematically sound definition, or positions and motion are ill-defined within the coordinate system. "Points on the Earth hold still" is a poor definition. Consider plate tectonics, which guarantees that a coordinate system perfect for Washington D.C will not be perfect for Berlin.
We, instead, start from ECI. ECI is centered on the centroid of the Earth. This is a relatively fixed concept (though technically changes infinitesimally when we send things to Mars). Anybody can measure the Cg of the Earth, so the center of the coordinate system is reliable. Now we need an orientation for the coordinate system. This is the equivalent of deciding which direction faces up on a map. This is trickier. We know we want an "inertial" frame, but that doesn't specify directions people can agree upon.
To deal with this, we sacrifice a bit. We get "close enough" to an inertial frame, in exchange for a measurable coordinate system. ECI notices that it has two rather reliable datums: the normal for the orbital plane for the Earth, and its rotational axis. Twice a year, at the equinox, these two align, creating a convenient measurement time that occurs every year. We arbitrarily pick the vernal equinox (rather than the autumnal equinox) to base our ECI systems off of. This does mean recreating the ECI frames requires observing seasons.
Now we get into the specifics. ECI is actually a class of frames. Each frame just changes how things are measured. Consider J2000, which is a ECI frame built from the equinoxs and poles of the Earth January 1, 2000 12 noon "Terrestrial Time." Note we even had to agree on a time to make ECI work!
Woof! Now think about ECF. ECF coordinate systems have to rotate, but we don't actually tie them to the earth. We tie them to a mathematically perfect Earth. We declare "ECI and ECF coincide at a date-time," such as Jan 1, 2000 12 noon, and that ECF rotates about the earth's rotational axis at a fixed rate: 7.2921150 x 10^-5 radians/s. This gets close enough to the earth's movement that we can claim spots don't move on the surface of the earth.
Holy cow! What was the purpose of all of that? Defining a coordinate system accurate to a kilometer over the galaxy will be hard, much less measuring it!
As a note: There are more systems than the ones shown. For plotting paths from Earth to Mars, a solar centric model is often used. This is a much more inertial frame, so longer paths are easier to calculate. There are also galactic frames used, which are usually specified via constellations.
Final detail: instructions. We don't always give instructions in coordinates, for the reasons stated earlier. They aren't always enough. We often give instructions in steps. It would be valid to say "go to Lat/Lon, orient yourself towards the tip of the mountain visible from there, and head that way. I'll be along that line." It's also valid to say "here is an ephemeris table describing my position over time. Go there." Instructions are complicated.
You will have trouble creating a map of the universe with 1km resolution. Consider a major issue: gravity wells. The universe is not flat. Those bends are going to matter a LOT if you want to see 1km resolution over a travel path of 41314127500000km. That distance, by the way, is the distance to Alpha Centauri, which is a relatively short jaunt by galactic distances. For comparason, that is like planning a trip from the moon to the earth, and trying to define a landing site within 10um!
Instead, we would do trips in steps. First we'd use a galactic coordinate system with poor resolution to jump into the right 1000 cubic light-year block. You would find your location using a best fit of visible stars to a 3d constellation map. Then we would take the time to acquire a more local coordinate frame to jump to the right star. Then we would probably use orbital mechanics to determine the right planet. Then we'd analyze landmarks on the planet to determine a local coordinate system. Then we'd jump down and survey to get to km.
The shape of these instructions would vary, based on what you are actually trying to do. Instructions on where a person is on a planet would be different from instructions as to finding an asteroid in an astroid belt (which may have collided with something since coordinates were read).
There's always PO boxes!