If this suggestion box is open to all ideas, I'm still endorsing the inclusion of regicide, myself (I can quote myself on an idea I posted elsewhere a while back).
As for the idea of Loyalty, I feel that loyalty shouldn't really be an issue in high-leveled, promoted units. Heck, I think it should be far from that. If a unit has survived for so long at the hands of the leader, they should be quite loyal to the cause and, personally, I'd feel irritated if my heroes started deserting me.
Perhaps, on the other hand, morale could be present. Morale would be increased for a unit if it won battles, recieved promotions, if a hero (or one of Bannor's crusading units or the Order's crusaders) was present, or (but only a little) if a unit in ajacent tile (or same stack) won a battle. Morale would be increased for all units if you 'won' a war (wiped out the other civilization or agreed to peace-terms where they gave you tribute), if you were in a Golden Age, if you built any wonders (military wonders especially) or if you killed an enemy hero (I'm thinking especially of Orthus or any of the dragons). Certain rituals would give a major bonus to morale (eg Glory Everlasting).
A soldier would lose morale if they lost a battle, were in a town under seige (maybe. When backed into a corner, some fight better, of course), if they were forced into retreat, if hit by magic, if diseased, etc. All units lose morale if certain rituals are performed (perhaps Blight, Bane Divine and Apocalypse especially? I don't think Wrath Unleashed would actually damage morale since I think it might greater inspire folk to take up arms.). Losing a war (if your civilization makes peace with an enemy and has to give tribute to them to gain that peace, this could be seen as 'losing').
High Morale units may fight harder, gain a first strike and maybe March or increased heal rate? High Morale might also cause enemy units to defect/be demoralised by the fervor of their enemies?
Low Morale causes units to be poorer fighters (and perhaps withdraw in the middle of combat) or, if attacked, to retreat akin to Loki with a significant portion of their health missing. Low Morale units who retreat from fights in either ways lower the morale of other nearby units (and raise the morale of the unit they retreated from). If morale falls too low, a unit may just disband itself or take up arms against its leader (become Barbarian or, perhaps, join an enemy army).
Being in a fort or city (especially one with walls/castle/palace) would cause morale to raise to a certain threshold (that could only be increased further by winning in combat).
Certain units, are immune to morale issues (specifically undead and golems and possibly demons though I somewhat suspect with them that, from vicious battle, they could at least gain morale to say the least).
Not sure if its a good idea (and its probably quite complicated) but its an alternative, perhaps, to Loyalty.
I really like the Battle idea here but, the problem is, you'd never know really who was attacking you then. Granted, if you see Elven archers attacking your troops it may be slightly obvious but if a Macemen whacks you over the head, you don't know where to point the finger. And I know, to some extent, its realistic and interesting to have a bit of paranoia in it. But in that case, wars are going to be pretty difficult to start if you don't know who's attacking you.
Perhaps, all units are identifiable outside your borders but can attack each other (instead of the Go To War pop up when moving into a square, it says 'Attack?' as an alternative to moving there peacefully) without declaring war. Doing so would give some diplomatic penalties to attacker ( -3 You attacked us on neutral ground and maybe a -1 "You spilled the blood of our allies/friends on neutral ground" for allies). So, though fighting in neutral territory would automatically open up a war, it'd spoil relations for the two powers and could, eventually, cause a war. Especially if those attacked are enslaved or were workers/settlers ( I can imagine a -6 "You killed innocent civillians!" which, I think, may automatically make a Good Civ go to war with the attacker whilst an Evil one may not be so concerned about civillian lives).