OK. But it’s still not clear. What do you mean by a sophisticated government, a kingdom? And by mini-city, do you mean low population? Maybe it would be easier if you specified which places you have in mind. Do you think any of the civs that were suggested in my other post (Kanembu, Benin, Kongo, Shona, Somalis etc) fit what you say? I don’t think so, and none of them were nomads either.
But why do these things count? Is there something inherent in them that makes a society more advanced or non-tribal? Malians did not use stones in their constructions, but mudbricks; does that make them tribal? Do all the civs in the game fit these requirements? As far as I know the vast majority of peoples built with wood, bricks and straw. Stone was restricted to specific buildings, as well as not being common to all areas.
Ironically, the suggested civs also fulfill these “requirements”: I know at least four of them had permanent capitals surrounded by rivers (the massive baked-brick walls of Ngazargamu in Kanem, and the extensive earth walls of Benin City) or on top of hills (stone walls for Mbanza Kongo and the Great Zimbabwe for Shona). The others I don’t know well enough, but, as I said, why would these factors exclude them?
Please read what I suggested first and then come back here. You yourself acknowledged that your research focuses more on the Sahara/Sahel area, so it makes no sense to talk about areas you don’t know about. Your statements are very vague and therefore worthless
But just to clarify: Kanem, Kongo, Benin and others had been praised for their sophistication by Arab and European visitors several times since their “discovery” until just before colonialism (when racism started to show up). Political, social and military organization, wealth, religious devotion, architecture, arts, economy and many other areas (all this you can see in the links I posted)
So again, read first. I think it’s just another case of ignorance.
(Of course, no one is to blame for not having heard of these things, but that’s exactly where I think the game can help. As a form of broad and popular media, it can generate interest for more discoveries)
The number of urbanized cities in Central and Southern Africa was indeed smaller compared to other places (due to ecological and other factors), but the few urbanized places that did exist were large in compensation. I don’t think this is relevant for adding a civ, but here is a thread that talks about the population of various African cities (including those of the suggested civs; it also has the dimensions of some of the walls of these cities).
But would this be a requirement? If yes, why?
You need to define the Middle Ages first. Do you mean the combo Feudalism + Christianity/Islam + militarized kingdoms? Or does it refer to the period ~400 (Huns) to ~1600 (Aztecs)?
All suggested civs have these things, except maybe the University in some of them (as far as I know). But the way the University is portrayed in the game, that’s no problem
I’m happy to help 
Fun fact: Hertog Jan is actually brewed in Limburg, so his conquest of that place seems to have had a long lasting effect. (Counter-fact: the borders were very different back then. The location of the brewery actually seems to have been part of Guelders.)