The southernmost airport in Greece would be on Crete. Iraklion airport is much bigger than Sitia airport, but Sitia airport may be a smidgeon more southerly. I doubt either has direct flights to Egypt though.
Edit: now that I’m on my laptop: these are the three airports in Crete.
Sitia Public Airport : 35°12′57.99″N
Heraklion International Airport : 35°20′23″N
Chania International Airport : 35°31′54″N