In ancient Greece, in place of “Sire” or “Your Grace,” how were people of stature addressed? Is there a gender neutral term?

The relevant monograph is: Greek Forms of Address: From Herodotus to Lucian (Oxford Classical Monographs) (9780198150541): Eleanor Dickey. See review at Bryn Mawr Classical Review 97.11.09 

The male defaults were anax/basileu (king), despota (lord, master), and kyrie (ditto). If you were talking to a king in antiquity, I think you just called them “king”: the familiar circumlocutions of majesties and excellencies are later inventions. LSJ says kyrie is late, and despota is what slaves used. Doing a search on the TLG, up to 2nd century BC, and skipping the Septuagint (which uses kyrie a lot), I find 96 instances of despota, and 9 of kyrie.

Kyrie “Lord” is of course the usual title for Christ in Greek (hence Kyrie eleison, “Lord have mercy”), as well as the usual rendering of Lord in the Septuagint—though despota turns up in Greek hymnography as well. My recollection is that despota was usual for Byzantine emperors.

For feminines, the best default I can think of is despoina, feminine of despota. It is a common title for the Virgin Mary later on.The feminine of kyrios, kyria, also appears to be post-classical.

Abstractions like “majesty” and “excellency” are late, like I said, and certainly in Modern Greek they are not used to address anyone. (Η αυτού μεγαλειότης “his majesty”, but μεγαλειότατε “most majestic one!”.) Which means that, since Greek has always had grammatical gender, there have never been any gender neutral terms.