‘Your Eminence’ in it’s current usage comes from the 6th century in Rome when the Latin phrase ‘Cardinalis Tuus’ was used as an address for the eminent clergy of Rome. It literally means ‘Your Eminence’ or ‘Your Chiefness’. It wasn’t until the absorption of northern Italy into the Carolingian Empire that Cardinals were invested with the civil status of a prince, civilly above the Comes (Count Palatine) but below the Emperor. It is actually the fact that the Cardinals were originally called ‘Your Eminence’ that ambassadors and high ranking princes now take the title ‘Eminence’ or ‘Eminent’.
I understand the variation amongst most English speaking countries. UK and some Commonwealth usage of ‘My Lord’ and ‘Your Grace’ derive from the historical origin of the majority of Bishops being from noble families in the Early Middle Ages due to the need for a rather substantial education and solidifying during the reign of Alfred the Great due to his heavy emphasis on reading and writing for both the Lords and Clergy. Tradition has brought this usage down to the modern day. This, however, is vernacular usage.
The American, Kenyan, Tanzanian, Ugandan and Philippine usage of ‘Excellency’ comes from the more traditional formal usage of the Latin ‘Excellentia’. By the decree by the Vatican’s Sacred Congregation on Ceremonial on December 31, 1930, the official address of a bishop is ‘Excellentia Reverendissima’ (the Most Reverend Excellency). In 1969, the Vatican made the ‘Reverendissima’ optional, returning the official formal address to ‘Excellentia’ (Excellency).