Definitely not an easy fix.
Don't be too downhearted Cmdr

.. for example, I don't think it would be too bad from a gameplay point of view if you were asked to target the system you wanted to supercruise to in the Galaxy map. Not only would you get a beacon to aim for, the game would have a way of knowing that approaching half distance between the system it knows your in, and your destination. It can then switch instance with some background loading, while you're miles from either place and don't really have a point of reference. As for paralax in skybox, on a galactic scale, with the exception of these two local stars (see next), paralax ought to be more or less negligible?
"Free roaming" (without targeting, and with the game picking automatically that you're in the influence of a new star system) is a bit more challenging from an instance switching point of view but I think it's still possible. From what I've seen (although not 100% certain) I think the skybox is generated from the galaxy map (or vice versa) and that they are linked enough to inform the game of your galactic coordinate between stars, from your stellar coordinate, and from that star system's known position/ origin. As you depart/ arrive at a system, galactic coordinate only needs a resolution that's "close enough," to feed you into the new system, with background loading, more or less in the right place.
From my understanding Frame Shifting is essentially using Einstein's Theory of Relativity that the result of an action taken is dependent on your frame of reference.
I think that's right, but it's still basically impossible to travel faster than light without some pretty exotic Physics. For the purpose of ED, frame-shift is a bit of madeup-ness that allows us to travel the HUGE distances without "speeding up time" (which other Elite games did) instead by going faster than light. In FE2 the "star dreamer" doubled, multiplied by four, x8 , x16 "time" (so the journey days (subluminal) passed more quickly. That couldn't be for ED because of multiplayer .. it would look I was typing REALLY quickly!