Short story, published before 1976.

Humanity has spread along the circumference of the galaxy (apparently avoiding the core), and diversified. The main characters are a married couple of a hairless race. They charter(?) a ship to follow evidence of alien intelligence (humanity having never found any before). The captain of the ship is of The Men, an all-male society who celebrate nature by always going naked. (One of the couple says, “I'd swear they sort their genes for hairiness. Did you notice he actually has eyebrows?”)

We track down the aliens and make contact. They like sulfur in their air, but upon comparison of biochemistry we find that they are humans too, whose ancestors spread around the galaxy in the other direction.

The two parties then turn their gaze to the Andromeda Galaxy, remarking that it's a forbidding project but we must do it.