Regarding gender as a social construct, I invite you to examine the life of
Dr. John Money and one of his more famous early patients,
David Reimer. Mr. Reimer was born male but his penis was destroyed in a botched circumcision. With a bit of surgical touchup, Reimer had the appearance of female genetalia, and the parents raised Reimer as a girl under the supervision of Dr. Money, who proclaimed the case a successful proof that gender identity is primarily learned.
Reimer failed to identify as female starting at age 9 to 11, and transitioned to living as male at age 15. After suffering from depression for years, David Reimer committed suicide at age 38. Dr. Money's 'successful' proof of gender as a learned concept has been used to justify the surgical alteration of damaged or intersex infants since then. More recent research involving twins and studies of larger populations reassigned as infants has shown a strong non-learned drive towards gender identity, with the twins research in particular pointing towards a genetic component. Here's a good
overview to start with.
Regarding your aliens, social stratification can happen without a gender-specific component, I think. Look at the caste systems that exist in most human societies, for example. People can find all sorts of interesting ways to sort each other into various categories and rationalize the superiority of one over another. We routinely do this by hair texture, skin color, place of birth, family wealth, and so on. In the past, things like height, physical strength, and handedness have been used to sort people into castes.