The Left Hand Of Darkness by Ursala Le Guin
Winner of Hugo and Nebula awards.
In a sense, this is a "first contact" story. Genly Ai is the first emissary from an alliance of planets wishing to establish relations with the world of Gethen. There have previously been secret missions to Gethen to gather basic information about the world. The first official emissary always goes to a planet alone, so Genly is a single man on someone else's world.
Gethen is in the midst of an ice age. The people of Gethen are the descendents of a long-ago colonization. They've changed considerably since then. They no longer have permanent genders. Instead, they have a monthly period of "heat" and while mating each individual will temporarily assume the male or female role. (People with permanent gender, such as Genly, are considered perverts.) Stranger still, they drink hot beer.
Genly must try to meet the people of Gethen, both to learn more himself and to introduce himself and what he represents to those people.
Clearly, it's not a typical first contact story - an isolated individual set down on a planet trying to sell the idea of interplanetary relations. It also goes beyond many first contact stories in the depth in can go to exploring the cultures of an unfamiliar planet. As one might expect if encountering an entirely new culture, some things remain mysterious or misunderstood for some time. This includes a system of interpersonal relations involving status, responsibility and "how things are done" - which the locals are not inclined to openly discuss. And there are matters to be dealt with such as Genly's "perversion" and other consequences of their differences.
In the course of the book he spends time in two rather different countries, as well as with a different sort of religious community. Since his goal is to convince the governing bodies of Gethen, we witness him experiencing the bureaucracies, intrigues, and changing winds.
First contact is not likely to be as straight-forward as establishing a language both sides understand, avoiding a few taboos and finding mutually beneficial trade items. Or at least not if we don't "gunboat diplomacy" on less developed planets. This is a good book for those interested in such questions.