Might be strange that we have sexes. Might also be strange that we only have 2 sexes. Many plants have two different generational types (haploid and diploid). Meaning each "generation" alternates between two different organism types. Fungi have both sexual and assexual reproduction [2]. But their sexual reproduction occurs when two cells directly fuse and then undergo meiosis into haploid spores instead of a diploid organism. Haplodiploidy occurs in insects where males are haploid by females are diploid [3]. Sex can be much more complicated than what it is in humans. Alien species may have even more complicated systems for genetic recombination.
Fungal sexual reproduction has more than two mating types, as well, which is apparently made possible by handling the mitochondria differently from animals. In animals, the two parent cells fuse and the male's mitochondria is destroyed. In fungi, the nuclear material is transferred between cells, and incompatible mitochondria never occupy the same cell.
So a species could have one type or thousands of mating types, and may be homothallic or heterothallic. Meaning that individuals of the same type could be compatible, or not, respectively.
In a dimorphic animal species, if you wander the wild and encounter a random member of your species, it is about 50% likely you could reproduce. For some species of fungus, a random encounter could be as high as 99.999% likely to be compatible.
We don't even need to imagine aliens for this. We have species right here on Earth that are incredibly different from us, and also available to be studied.
> Many plants have two different generational types (haploid and diploid).
For the vast majority of plants, these are not physically separate organisms. The key difference here is that the haploid cells of the plant can themselves undergo mitosis, which animal gametes cannot do. Since we generally consider cells with different genetics to be different individuals, we speak of plants as having alternation of generations.
For the most part however, the haploid cells live in the diploid organism or vice versa, depending on which branch of the kingdom you're considering. It's not like botanists run tests on a particular specimen to determine its ploidy. For any given species, we know what the ploidy of the individual is. For example, flowering plants are all diploid. If you find a flowering plant, the individual has two sets of chromosomes, but somewhere in its tissues there is a haploid cell (descended from the parent) that is undergoing meiosis, and is thus a separate organism.
[1] http://sciencelearn.org.nz/Contexts/Ferns/Sci-Media/Animatio... [2] https://www.boundless.com/biology/textbooks/boundless-biolog... [3] https://en.wikipedia.org/wiki/Haplodiploidy