I was thinking about the game "Stellar Conquest", but I could SWEAR that either Metagaming Concepts or another company had another big-box science fiction board game which boasted actual 3-D movement I remember that they had larger hexes, but within each hex, were these round dots of different sizes, and the size /position of the dot determined the location of ships and star systems on the Z-axis.
I know that I owned the game and tried playing it at least once. At the time, I thought it was very clever how they did the 3D portion of it, although it was kind of a mind-bender as far as tactics were concerned. I just can't remember the name.
I believe the game you refer to was called Godsfire, and it was published by both Metagaming and Task Force Games.
I owned it at one time, but never got to play it.
Here's a picture of the 3D movement squares