Well, this is an interesting challenge to be sure.
First, the hemming--I have to wonder why in fact, this region never did develop as any kind of really major civilization in world history under any sort of society, even one deeply derivative of other "cradles," let alone under its own steam. Not only were there Greeks and Romans all over at least the western shores of the Red Sea (not to mention the Egyptians themselves there for thousands of years) but even before the rise of Islam there were of course the Arabs, right there on both the eastern shore of the Red Sea and all along the south coast of Arabia. Then they went on to found a continents-spanning ecumene of civilizations. And they certainly did expand south along the east African coast as well as sewing up the sea trade to both the Persian Gulf and India. Yet with Pharonic, Ptolemeic, Roman, and Arab civilizations right next door and all interested in trading and perhaps expansion in at least one direction this sea/land crossroads offered, if not all of them at once, still the region remained just that--a cross-roads, not a cradle.
I suspect you have to take a hard look at why and how Greek society developed as it did. Greece like the Horn region is at a crossroads, to be sure, or rather a jumping-off point near older, initially richer civilizations but also along expansion routes to less developed regions which they both traded with and colonized. So far so good. But two things--first of all, I think the "cradle" land you want to consider is considerably less fertile than Greece. Of course Greece is rather barren itself, particularly after being largely deforested. But while its barrenness and rugged terrain stimulated seafaring--for fishing, raiding, colonization, and also trade, while the dissected terrain favored small, local polities over big centralized empires--still there needed to be an initial foundation for the early city-states to grow on. The Athenians considered themselves mainly in debt to the goddess Athena for her mythic gift of the olive tree. One can't live on olives alone, but, growing on land otherwise largely useless for agriculture they livened and enriched the diet, and eventually served as a basic stock in export trade (mostly in the form of olive oil). Greek trade also was deeply rooted in selling wine overseas--a less unique product, but one that Greece could specialize in.
Where are the gifts of an East African Dionysus and Athena, that the people of the Horn region could use as foundations of their initial subsistence and then trade? I think right here we have one reason East Africa has always been a crossroads--it's barren country. Perhaps if the Ethiopians could have started exporting coffee earlier? But even then, the East African coast is merely a transfer point at best--and indeed Arabs did start trading in coffee, and establishing plantations elsewhere, and the southern mouth of the Red Sea remained just that--with rather vibrant cities on the east coast, in Arabia, but not so much on the African coast, despite their closer proximity to the original source of coffee. (And by the way, Ethiopian coffee, at least the cups I have enjoyed at Ethiopian restaurants, is really really good coffee! There is still, after something like a millennium of development and spread of the crop, a significant advantage in going straight to the source!)
Second, Classical Greek civilization did not spring straight out of virgin soil, like Cadmus's army sown from dragon teeth to legendarily found Thebes. The classical Greeks themselves remembered they were the descended from the Myceanean civilization and, grudgingly, that that was derived from the Minoans. I don't know if this point is worth dwelling on too much, but I suspect it has some bearing--very possibly, to get a situation in East Africa roughly parallel to the Greece of the early Classical period, you may well need some layers of earlier empire in their backstory. So you would really be exploring not one alt-timeline society but two or several. None of which existed OTL except as roadside services on other people's highways.
Now for the hawing--is "hawing" in any sense opposite to "hemming" or is it just more of the same?
Anyway I think it would be cool if you could pull this off. One feeling I have about it--if it could happen at all, it would happen well before the Classical Greek period, and would very possibly pre-empt--excuse me, I 'm still new around here, "butterfly away"--that whole thing, or at any rate drastically change it. Seeing the Horn region as a crossroads, two of the three directions you can go from there go straight to the most ancient civilizational regions known to history--Egypt and Mesopotamia. (With the mouth of the Indus River one hop further east.) In fact, Yemen is very likely the most ancient spot of human settlement outside of Africa itself--the ancestors of everyone who isn't more recently African probably crossed from Djibouti to Yemen when the sea levels were much lower, and from there their descendants colonized along the shores to India and only later branched north into Eurasia. So, both in terms of long-term human occupation and proximity to the most ancient civilizations you can't get much more ancient than the Horn region! This merely raises once again the question of how come we don't generally hear much about this region as a center in its own right, which has had longer than just about anywhere to claim such attention. But if you can do it, I'd guess it could be just about as far back in time as you like, within the past 8000 years or so. And if it's any time before 500 BC, the Greeks would become peripheral also-rans, because the East African version of Alexander would surely lock up Egypt. And probably do it long before Homer's poems would even be written down, if not before the real Trojan War.
Perhaps then a skeptic like myself would be dismissing, but a thousand years ago, the possibility of any really deeply historically significant society arising on those barren islands and peninsulas on the north shore of the Eastern Med, where they only have olives and vines, but none of the really vital stuff everyone knows comes from East and Southeast Africa?
Then again, though less probable, it could also be fun to have the two regions, Greece and East Africa, rising in parallel at pretty much the same time, with Persian-ruled Egyptians bemusedly answering the impertinent, skeptical if sometimes awed questions of both Greek and East African coastal tourists--who would most likely run into each other right there on the Nile. Would the two upstart peoples recognize a kinship in spirit that draws them together in collaboration and doubles the reach of a united Classical era, or would they despise and fear each other as rivals--the way Greeks and Romans regarded the Phoenicians?
Speaking of Phoenicians, what if the East African Classical city-states and their expanding colonies/traders/mercenaries get started only somewhat earlier than OTL Greece, but find, on the other side of Egypt or via Palestine, Phoenicians, and link up with them? I think that would very clearly butterfly away Greece as a regional dominant culture, and probably the Romans into the bargain.
-------
And now back to hemming again--
I reread your original post, Midas. It reminds me you aren't tightly focused on any one candidate Greece-sized region, but just asking "could there be a Greece-parallel anywhere between the mouth of the Red Sea and the southern reaches of the 'Swahili Coast.'" Is that a fair paraphrase?
Well, clearly we tend to focus on the north end of that range, to be near the "crossroads," and tend to reserve the southern regions for the eventual expansion, analogous to the Greek colonization to the West that brought about Sicily, Magna Graecia, Marseilles, as we know them. And so strongly influenced Rome. I see you claim there are enough fertile regions interspersed with barren ones along the coast that somewhere there ought to be a Greece-type region.
Again--while I don't want to slight the potential of East Africa (which, inland, is where we all evolved, after all!) I have the telling impression that while much development did eventually occur there, along the coast it was mostly trading posts of larger civilizations based elsewhere, writ more or less large. Inland I know of at least a few examples of civilizations less beholden to outside power--Egypt itself, Sudan, Ethiopia, Buganda, Great Zimbabwe, scattering far across both space and time--but I am not aware of any of these finding their own way to the coast and then launching ships along it, or even stimulating some local shore-dwellers to take up the role of mediating in such a coastwise trade. That role, as far as I have ever read, has always fallen to foreigners coming into Africa from the sea, and they or their proxies did the finding and trading with the inlanders. Again--I have to wonder why, and suppose that in some sense, either in terms of fertility on or very near the coast, or the perhaps challenging nature of the coast itself for shipping (until one masters the art in more forgiving waters), the land itself strongly discourages such developments.
Certainly, however nice the tropical and southern shores of Southeast Africa might be, I have the notion that right near the Horn and toward the mouth of the Red Sea, those shores are tough to either live on or navigate around.
But as I say I'd be fascinated to be proven wrong!