You are being confused by a naive idea of species. You are implicitly taking "is the same species as" to be what mathematicians would call a transitive relation like "has the same number of legs as". So if Adrian has the same number of legs as Beth who has the same number of legs as Charles who has the same number of legs as Dawn who has the same number of legs as Edward who has the same number of legs as Francine, who has the same number of legs as George who has the same number of legs as Heidi, then it follows that Adrian has the same number of legs as Heidi.
But a relation does not
have to be transitive. Consider the relation "lives in the same neighborhood as". It is perfectly possible for Adrian to live in the same neighborhood as Beth, who lives in the same neighborhood as Charles who lives in the same neighborhood as Dawn who lives in the same neighborhood as Edward who lives in the same neighborhood as Francine who lives in the same neighborhood as George who lives in the same neighborhood as Heidi --- and yet for Adrian and Heidi to live in different neighborhoods.
"Is the same species as" is a relation of the second kind. One can see this by considering that for two organisms to be the same species, they do not have to have
identical genomes, just genomes in the same "genetic neighborhood", as it were.
---
About the evolution of sex --- there are organisms which can either reproduce sexually or asexually. Anlso, there are organisms which can reproduce asexually or in a manner that involves lateral gene transfer, which may be considered a more primitive form of sex.