According to my friend, all societies everywhere have had gender roles. The strength of the demarcations and where the lines are drawn, however, and whether there is a set of occupations where it doesn't matter, are variable.
So for instance in almost all pre-industrial societies care of small infants is a female activity, hunting large animals and/or agriculture with large draft animals is almost always a male activity. (Basically, as a rule of thumb, ask yourself "in a society with no contraception, could a woman in the third trimester of pregnancy or with a toddler on her hip do this particular activity?")
But there are occupations in the middle which get allocated differently in different societies - e.g. for the Navajo in California, weaving was traditionally women's work, for Medieval society in the SW of England, weaving was traditionally men's work. And of course there's the issue of what happens when someone transgresses boundaries - a widow who for instance continues with her husband's weaving business because it pays more than spinning (traditionally female). Is the reaction "ah she's a bit odd, but at least she's keeping the children fed" or is it "stone the witch!"? The former would be a society with reasonably flexible gender boundaries, the latter one with rigid boundaries (in anthropologist speak).
Interestingly, this doesn't necessarily correlate with women's status within the society. The Iroquois, for example, had fairly rigid gender roles, but women owned the farm land, passed it down to their daughters in a matrilineal inheritance system, and wielded political power (including being able to veto decisions to go to war with neighbouring tribes).
In this sense, the existence of third genders as a social category culturally specific to a particular group of people does seem to correlate with that society viewing gender (in the sense of socially-sanctioned roles and behaviours appropriate to one sex or the other) as a rigid thing, rather than a looser and more flexible set of rules (most people live in these boxes but we tolerate exceptions). Bacha posh in Afghanistan, for instance, would fit this - a rigid set of roles, but families with no boy children (seen as a disaster in an incredibly patriarchal society) can bring up a daughter as if she was a boy - though she has to revert after puberty. Or sworn virgins in Albania - can live their whole lives as men so long as they don't have any sort of romantic or sexual relationship. Probably the ethnographic groups where this has been studied in most detail are N American tribes, and again, there seems to be this correlation between rigidity and third genders.