Nine Hordes

Civilization is a mistake - it is the core belief of the forces of the Nine Hordes. It brings peace, and peace brings weakness - and weakness brings war, but one for which those weakened by the peace are ill-prepared at best. Nine Hordes seek to amend that mistake and restore themselves to the state before that insidious corruption crept in. They are heirs of what once was common to the lands of Karadia - tribal and nomadic styles of life, close to nature and without wealth and safety that corrupts and sows weakness. They live in the Lost Lands, seeing it as the best way to temper themselves (and because if they try to settle anywhere else, well, the Grand Empire doesn’t like that at all).
They have a bit of a love/hate relationship with the Grand Empire. Their specialized magic users (shamans and wrathsingers) are the only ones among the servants of the Fallen that aren’t killed on sight. That's because lack of supernatural corruption typical to the Nine Hordes makes some a lot of theologians and scholars question whether the Nine Hordes have actually Fallen - or are actually exarchs that seceeded from the Pantheon in search of a different way of life to grace with their patronage.
Nine Hordes are essentially unpredictable, but not in the same way as the forces of the Shadowlight Covenant or the Rapturous Ecstasy. Rather than using a diverse list of means to screw the Grand Empire, Nine Hordes are busy surviving and carving themselves a niche in the ever-changing Lost Lands. Their warriors are as likely to invade the Empire to pillage and enslave as they are likely to get hired by its client states as auxiliaries.
As a result, the relationship between the Grand Empire and Nine Hordes varies depending on the exact area in question. Sometimes it’s war, sometimes it’s a cold war, sometimes there is some sort of tribute to keep the tribes (or the Empire) from attacking the other side, and sometimes there is actual cooperation. Their lack of homicidal anger towards the Grand Empire only further strengthens the 'non-Fallen' theories.
The titular Nine Horde refer to the major species (or subspecies) in the Grand Empire that has appeared to have chosen the preferred lifestyle of the Nine Hordes. Those are humans, elves, beastkin, ogres, goblins, orcs, giants... and the two species that are unknown. Some speculated it's either the now-corrupted razors, the isolationist dwarves or perhaps species that never existed in the Prime Material World or are yet to be born there.

Structure

The Nine Hordes have only a single type of leadership. The one born from personal might. There is always a warlord (or warchief or whatever other title he or she bear) that is leading the tribe. Sometimes permanently. Sometimes only during the times of war. Sometimes there is a council of elders or shamans to assist the leader. Sometimes not. In the end, the structure varies greatly from tribe to tribe. The Nine Hordes themselves do not care for that.
Above the level of tribes in the Material Worlds the situation is... actually entirely identical. Sure, some details change, but as a whole, it's always the 'might makes right' combined with 'you kill it you take it' approach to personal promotion and personal possessions. Warriors (spirits, the souls of the dead or whatever else lives in the Spiritual World) will typically flock to whatever powerful warlord that can guarantee them their rights (and offer an option to pillage weaker tribes).

Territories

Tribal Lands - Unlike other Fallen, the Nine Hordes do not bother maintaining empires in the Lost Lands. Instead, the majority of their forces have either settled down as independent tribes (either united or separated into a handful of clans) or are travelling around the Lost Lands in circles as nomads. They are commonly divided into numerous clans, who are tied together with promises of common defense and some holy places where they occasionally gather.
Majority of them are warriors, regardless of gender. Living in the Lost Lands keeps their blades sharp, and easy access to magic-enhanced meat of beasts inhabiting them keeps them way stronger than they should normally be. In fact, many of them don't even bother learning martial arts, instead relying on their physique - the more accomplished warriors of the Nine Hordes can reach truly ridiculous level of strength and resilience, one that makes them far surpass the non-Nine Hordes members of their own species.
Fields of Blood - A Spiritual World of endless plains (and occasional forests), where blood rains from the skies and fills the rivers and lakes. The tribes inhabiting it constantly fight each other to prove their strength, with the strongest allowed entrance to the Palace of Blades - a massive structure pulled through the Fields of Blood by diminished forms of old gods and their most potent servants defeated by Saevius himself during the Dawn War.
This is a place where only strength matters, but it isn’t the only thing that happens there. In a way, it is the closest this universe has to a warrior heaven (especially the Palace of Blades, where the strongest of all warriors are allowed to tread). There is no true death there, only countless contests of strength and bantering together about their result. And, occasionally, a bloody murder of someone crazy enough to invade the fields of blood.

Military

Valkyries - According to scraps of surviving lore, these winged female warriors carried souls of worthy warriors to the afterlife of one of the many pre-imperial religions that fell to the ascendant gods of the Empire during the Dawn War. There were about thirty of them, all of them apparently virgin. Now there are way more of them, all of them serving Saevius, the imperial Hierarch of Conquest - and regardless of how weak they are, they all appear to be his far descendants. How exactly that came to be is anyone’s guess.
There are wild and ferocious warriors, attracted to prowess in battle and the tally of slain enemies. They do not really carry souls anymore, but they often appear on the Material Worlds to serve and assist the greatest warlords of the Nine Hordes, a rare recognition of skills indicating an attention of Saevius himself. Especially as they will gladly use their position and influence to steer 'their' warlord into an ever greater feats of bravery (that also happen to play right into some unknown long-term plans of the Hordes, although in all honesty nobody's sure if there is such a thing).
Junk Warriors - Saevius is, in a way, just. He respects wrath, lust for power and the desire to kill your enemies just as much as the very act of killing if someone is rendered incapable of following on them by outside influence. Junk warriors are believed to be the Dead that harboured particularly delightful wrath yet were crippled in life, rendered forever unable to act on their rage, yet still feeling enough hatred that they simply couldn't end in a nice afterlife.
Now they have bodies partially made of metal (with many sharp edges), and are absolutely, completely and homicidally insane even per the Hordes normal standards. They tempered their wrath a bit too long, and have themselves to it completely. Some of them - those whose wrath was the strongest of them all - are now many meters high engines of destructions, proceeding in the vanguard of supernatural Hordes’ forces. There are even cases of junk warriors that has manage to control themselves despite their raging anger by having equally potent willpower - the result is typically even more terrifying than the largest and craziest of normal junk warriors.

Religion

High Gods

The Nine Hordes follow two high gods. The first one is Saevius, the Hierarch of Conquest, high god of rage, slaughter and war - a crazed conqueror who is said to have slain a great number of gods during the Dawn War and seems to enjoy gathering trophies. The other deity is Dolositas, the Hierarch of Deceit, high god of deceit and taking what belongs to the others, and also brain to Saevius' brawn.
Together they represent what is expected from a proper follower of the nine Hordes - both cunning battle plans and fierce brawl, both berserkers' rage and a successful stealing of everything that's not bolted down (and then finding something to get the bolts out).

The Fall

Supernatural corruption, so common among the Fallen, is absent entirely in the Nine Hordes. Its tribes are willingly following the Hordes, with no signs of coercion or mental influence. This means that they have relatively low number of converts, but there are still some who willingly chose that lifestyle.