i think you should stick with 2d flat out.
From having played games with 3d strategic maps, they're more trouble than they're worth.
The only real trouble with the 2d is the clustering and I believe that either futzing the generation or fiddling the stars around manually will be plenty sufficient.
From a graphics point of view I agree with this, which is surprising because the lack of 3D in space games drives me nuts.
If you were willing to go to a full 3D viewport (using XNA, for example, which you can't use 'cuz it's in C#/.NET and you're using VB6), then I would consider going 3D, but this is because you (or users) could then rotate the view to let the brain's circuits kick in and give depth perception. Without that, you're kind of toast. An alternative would be to color-code the names with a depth dependent color (red-high, blue-low, or vice-versa), but then you'd have to have a good query tool to give precise distances.
Reading back through the thread (oh, look, color-coding was suggested), I see you worrying about clustering around Sol. That's because you're using a sphere as the selector for what's displayed. This is a mistake - you should be using a cube as the selector (in the same way you use a square for the viewport, not a circle). If you use a cube, with total depth equal to the horizontal distance displayed, then you shouldn't see any particular clustering in the center.
So the alternative (I think) is to display a cube, with names (and/or dots) labelled with zoom-dependent color that goes through the whole spectrum, with blue near the top of the cube and red near the bottom (or vice versa). This really works a lot better though if you can rotate the view, since that gives separation between stars that get unlucky and lie on top of each other.
If you don't go 3D, then I would just smoosh everything down into the plane. This avoids the weird clustering effects away from Sol. Since you're already not going 3D, you're only in "Almost Real Stars", and it's no big deal to go from 3D to 2D (other than the fact that it's easier to envelope an enemy because the circumference of a circle goes like R, while the surface of a sphere goes like R^2). Interstingly enough, smooshing gives you
exactly the same view as the cube ideas.
Ok, here's a weird idea, which might be the one you're already talking about. As far as I can tell, you've proposed changing the actual positions of the stars to rotate them into the equatorial plane, keeping the bearing the same, to generate a new set of 2D locations for the stars. You also mentioned Mercator projects. What if you kept the star locations 3D, but used your rotation trick to generate a 2D Mercator-like "distance" view centered on whichever star happens to be picked (not just Sol). You could still use the color code to flag which stars have actual locations that are either high or low. So white would mean "in the equator - not distorted", blue (because blue-shift is coming at you) would mean "above the equator - actually closer to Sol in xy" and red would mean "below the equator". You could then have two different modes of the map - one undistorted with color-depth coding, and one "distance". Having a quick toggle between modes would give the brain an additional cue for picking out depth. This means that your actual locations would still be exactly correct, but the distance view would simply be a distorting visualization centered on a star, like Mercator.
Note that, from my point of view, I'm MUCH more interested in 3D in the tactical map than in the strategic/galactic. I think Elite's system (with lines into an equitorial plane and rotation of views) is the best I've seen.
John