I was thinking about improving the faction system, as it strikes me as far too modern and consolidated for a Medieval-themed game. IMO, the whole concept of factions should be dropped. That's right, no factions. At least, in the current meaning of the term.
Instead, introduce a complex vassalage system. It would work this way. Introduce five "ranks:" (names subject to change)
knight (owns no property)
duke (owns a village)
baron (owns a castle, or owns a village with a duke for a vassal)
prince (owns a city, or owns a castle with a baron for a vassal)
king (owns a city and has a prince for a vassal)
The way someone starts the equivalent of the factions we have now is to request people to swear fealty to him. They become his vassal and join his "faction" color, similar to how it worked with factions. The top guy gets to name his Duchy/Barony/Princedom/Kingdom like you can name factions now. Depending on the quality of settlements you own, you would automatically go up in rank. (for example, you capture a castle and you automatically go up from a Duchy to a Barony.)
In addition, the duke/baron/prince/king would only be able to control his own settlement. His vassals control the lands they own but pay a small tax to their lord. If a vassal conquers a territory, they can opt to either a) keep it for themselves, b) give it to the king, or c) bestow it on a vassal of their own.
This will create a tiered vassalage system like Feudalism was in real life. For example, in a kingdom, one of the barons might obtain some more land and bestow it on a vassal, independent of the king.* This vassal pays a small tax to his lord, and so on, down from a king to a duke and knight.
Is your vassal not cooperating? Too bad, that's part of politics and a relationship-based system of government. Go raze his castle to the ground and show him whose boss. Okay that's a little over-the-top, but you get the point. Civil wars, discord, etc will be able to happen if you don't know your vassals. It will hurt big clans in some respects, but also provide a lot more internal strife. The game won't just be faction A attack faction B. It might be the king of kingdom A attacks kingdom B, but some of kingdom B's dukes break off their allegiance and side with kingdom A. Or, a full-blown civil war within a single faction.
You should have the option of offering vassalage to defeated enemies (but again, pick wisely). Vassals could decide to break off from your faction, and they take their lands and armies with them. The faction leader won't have absolute power to do whatever he pleases.**
*for the sake of gameplay sanity, the king should have to approve the decision, else it will be chaos with too many people entering the kingdom.
**as a caveat, vassals should have the option of giving their liege lords control of their lands. This should be done for gameplay reasons, since we all don't play 24/7.
For example, some guy (we'll call him Bob) wants to play with his clan buddies together in strategus. He declares himself a knight and invites his friends (or they request) to become his vassals. Their rank is knight. Bob conquers a village, he gets promoted to duke and starts the Duchy of XXXXXXXX. His knight friend conquers a village also and is promoted to duke. This promotes Bob to the rank of Baron. Baron Bob then conquers a castle and gives his first village to one of his knights. et cetra. They build up a kingdom, each of his princes and barons have vassals under them, etc.
tl;dr version:
add a Feudal system of government. Have ranks, with each rank having vassals under him/her. It will add more depth to the faction system and create intra-faction fighting and more fun (and drama, we all love e-drama).
