Squares significantly distort distances; worst case is using 1 movement point for 1.4 of distance, and average case is moving a distance of 1.2 per 1 mp. With hexes, the worst case is that you spend 1.15 less than actually traveled, and average case is 1.05. Hexes are significantly closer to reality in terms of distance to MP required.
This is a valid concern if your tile grid is attempting to accurately depict absolute distances on a flat plane. However, I don't see how this matters for Galactic Civilizations, where it is possible for a planet in the orbit of one star can be closer to a planet orbiting a different star than the planet is to its own star or any other celestial bodies orbiting its star. Distances in Galactic Civilizations are already so heavily distorted from the absolute distance that the difference in absolute distance traveled on the tile grid is not worth worrying about.
This is also something that can be solved by using differing movement costs, which is something entirely practical for a computer game because the computer can take care of keeping track of the numbers. Making orthogonal movement cost 2 points and diagonal movement cost 3 points comes fairly close, and wouldn't be that difficult to track even if you were doing it by hand (especially over short distances), and a computer could easily track movement costs of much greater accuracy.
Hexes tessellate better into all other regular polygon shapes. That is, the percentage of "excess" or "missing" area when using hexes to approximate circles, arcs, hemispheres, pentagons, and even most quadralaterals is much less than when using squares (presuming the hex and square have similar face-to-opposite-face distance).
If the size of the polygon that you're tessellating the squares or hexagons into is much greater than the size of the squares or hexagons, it really doesn't matter that much. Moreover, when in Galactic Civilizations do I care about how well the tiles tessellate into a circle? Starbase area of effect is about the smallest one that you care about, and that circle already has a sufficiently high radius that the error isn't much to be concerned about.
Why not try Octagons ? They are more visually appealing and to my way of thinking offer much improved "tile" movement although I've not tried to form an octagonal grid to see if it actually is build-able.
Hexagons are the regular polygon with the greatest number of sides which can tessellate into a planar grid composed only of one shape. If you tessellate with regular octagons, you'll need to have square tiles mixed into the grid.
the only way this works is if we assume that gc2 actually used an octagon grid which was represented in squares.
Or, you know, if you don't assume that the grid maps to the space being represented without distortion. Because clearly those planets you occasionally see only one tile away from one another when they orbit different stars really are that physically close to one another. You're using a 2D map of 3D space which clearly has incredibly distorted the distances between various points (not to mention how much the map has to have distorted space to map the various stars onto the same plane in the first place), and you're worried that the absolute distances between a couple of points on the tile grid doesn't line up with the number of movement points it takes for you to cross that distance? It's not like there aren't ways of distorting a rectangular grid in order to make it work; just take a look at a globe or any flat map of the world.
Heck, Civ5 was the first in that space to finally get Hexes, and it was wildly popular, for the above reasons.
And one of the most popular map projections used in the present is the Mercator projection, which uses a rectangular grid to preserve relative bearing from one point to another but makes no pretensions to accurately represent the distance between points on a uniform scale (unless the points are at the same latitude and you're measuring distance along that line). If you're trying to map a spherical surface onto a flat plane, you really need to decide first what you want to preserve, because you have to sacrifice the accuracy of something in order to make the projection.
If you're going to complain about the way a square grid distorts movement costs, you shouldn't bring up Civ5, which maps a presumably spherical body to a regular hexagonal grid, as evidence of how great hexagons are at preserving the distances. If you want a grid of regular hexagons mapped to the surface of a sphere, then some of those hexagonal tiles in Civ5 should only be adjacent to five tiles and the strips marking the North and South poles should come fairly close to being a single tile. If your map is just looking at, say, Africa, then the grid of regular hexagons might be fairly close to accurately portraying the distances, bearings, and connectivity between points on the continent. If you're looking at the planet as a whole, the hexagonal grid really isn't any better than a square or rectangular grid.