working off your idea, Skeetles, here is what i would suggest:
Suggestion 1: a Rhun fortress as the base fortress, since most of the people commenting on this thread seem to agree with Rhun being more "stable" as opposed to Harad's more nomadic culture. The outposts can create two different camps: a Rhun camp and a Harad camp. They would both act like the regular outposts for Gondor, Rohan, Isengard and Mordor, with three build-plots on them.
The Harad camp would build the Haradrim Palace, the Umbar Tavern and the Mumakil Pen. The Harad camp will be like the one in BfMe1, which trains Haradrim units: Archer, Spear-Thrower, a Mahud half-troll elite warrior and the Harad cavalry. The Mumakil Pen would, of course, train Mumaks. The Umbar Tavern (or you can make a more Byzantine-style structure, reflecting Umbar's place as the former trade center of the Numenorean civilization at the vanguard of Haradwaith, just as Constantinople was the trade gateway for the Eastern Roman Empire on the edge of the eastern lands in the real world) would train Umbar corsairs (the ones from the standard BfME2) and elite archers (as Umbar, especially in the films, is depicted as a ship-fairing nation, long-range archers would be most useful firing from the decks of their black ships).
I feel that the Variags of Khand, as they are the one sub-faction with the least known about them according to the official lore (and not even appearing in the movies), should be represented on an expansion plot building, similar to the Ranger Tents or Beorning Hut. While I know that the Edain Team is rather fond of the Lord of the Rings table-top game, I found the bushido-samurai style of the Variags therefrom to be a bit too real-world recognizable. I would recommend, since "Variag" is similar to the real-world word "Varangian", the Variags of Khand would be a nomadic Black Numenorean sub-faction, almost like super-evil Norsemen (the book also describes them with axes and beards like Dwarves).
Suggestion 2: since this is a faction of Evil Men, we start off with a no-walls Black Numenorean fortress, representing that the Black Numenorean servants of Sauron (like the Mouth of Sauron) were the ones that brought the Men of Darkness back under the sway of Sauron. then, in similar fashion to the Dwarves, you can choose whether to have Rhun or Umbar as the main faction. the main problems with this suggestion would be the lack of originality, since this would be a repeat of the Dwarves, and that it would require expanding Umbar, since having a massive Harad fortress would be unlike their nomadic nature. also it would probably be hard to have the AI use this as well.
Additional suggestions about units and their roles:
Rhun:
Easterling Swordsmen - light melee unit
Easterling Pikemen - anti-cavalry melee unit
Soldiers of Rhun - elite anti-cavalry melee unit
Balchoth Lancer - light cavalry
Rhunic Cataphract - heavy cavalry
Wain-Rider - elite ranged cavalry
Blue Acoltye - elite spellcaster/siege unit
Khand Subfaction:
Variag Berserker - elite melee unit
Harad:
Haradrim Archer - light ranged unit
Haradrim Spear-Thrower - elite ranged unit
Mahud Half-Troll - elite melee unit
Haradrim Cavalry - medium cavalry
Mumakil - elite ranged cavalry/siege unit
Umbar Subfaction:
Corsair of Umbar - elite melee unit
Umbar Archer - elite ranged unit
The Easterling Swordsmen would fit into the first suggestion, filling in the role of light melee unit that, until now, Rhun has been lacking. The Blue Acolyte would be based on what little we know about the Blue Wizards, with one rumor being that they founded (unintentionally or not) magic cults during their ventures into the East. It certainly seems to be the most fantastical element here, and would seem more fantastic on the field of battle, throwing fire-balls to tear down fortress walls, but my thoughts on this matter were to have a siege unit that was wholly unique and not just another catapult (the Haradrim have the Mumakil, which could very much be used as a siege unit as well as a troop carrier and walking garrisonable tower). Other suggestions for a more "realistic" Rhun siege weapon are welcome.