There was one instrusion of non-Indo-European into this vast geographical expanse, and that was the Semitic family of languages. Today the best known Semitic languages are Arabic and Hebrew. Back in the days of Nicolaos and Diotima, by far the most important Semitic language was Phoenician. Beginning with The Ionia Sanction, Nico will start to hear Phoenician being spoken about the place as the hangs out around sea ports. The Phoenicians were massively successful sea traders.
The Phoenician language had an immense influence on world history, not because of anything about the language per se, but because at some point, some Phoenician genius decided it would be cool to write down his language, so he came up with this alphabet:
There's unicode support for Phoenician, believe it or not, but not even recent browsers support the extension so I was stuck and had to insert the letters as images from wikipedia.
As with all things involving the word Semitic, there's a lot of argument and politics involved, but it's apparent there must have been a Proto-Semitic language from which the others descended, just as there was a Proto-Indo-European language. Proto-Semitic probably began in Africa, because Semitic is part of a much larger family called Afroasiatic. The cognates (similar words) between the Afroasiatic languages are very much looser than the close connections between Indo-European languages, but still good enough to show family groups. Semitic is the only part of the family found outside Africa. The oldest recorded Semitic language, as far as I'm aware, is the Akkadian that was written in cuneiform on clay tablets. The cuneiform was borrowed from Sumerian, which definitely was not Semitic (this is sort of like the LinearA/Linear B situation). The closest living relative of Phoenician is Hebrew. Arabic derived from a southern variant of the same family.