It has been suggested that the fundamental haploid-diploid cycle of eukaryotic sex exploits a rudimentary form of the Baldwin effect. This paper uses the well-known NKCS model to explore the effects of coevolution upon the behaviour of eukaryotes. It is shown how varying fitness landscape size, ruggedness and connectedness can vary the conditions under which eukaryotic sex proves beneficial over asexual reproduction in haploids in a coevolutionary context. Moreover, eukaryotic sex is shown to be more sensitive to the relative rate of evolution exhibited by its partnering species than asexual haploids.