Select id, nome, link genere
from tabella
order by genere, nome;

con questa query hai un recordset ordinato per sesso. Fai un controllo sui sessi, quando questo campia stampi un optgroup!

Ogni riga sarà:

<option value=' $rstLink' >$rstNoME</option>