The Phantom (of the opera) - Invisable Barbarian Hero
Enters game near the advent of theatres (Perhaps appears when X number have been built). Is invisable, and will enter cities with theatres in them "Haunting them". The theatre stops producing bonuses and produces bad negative effects, like +4 unhappiness, and maybe -10 gold. The way to get rid of him would be to use units that can see invisable units and "attack" him - at which point he is randomly transplanted somewhere else in the world - and then will huant the nearest available theatre, ad infanitum.
Cthlototh the Wicked: Level 3 Archmage Barbarian Unit.
Appears mid to late game. Has Mind III magic. Never suffers adverse affects of Dominate.
Any unit attacking and failing to kill Cthlototh becomes immediately dominated by Cthlototh.
Moire of the Black Vale: Immobile Unit placed in a Barbarian city.
Enters Mid Game
Moire Generate's random "Great Villians". THese are essentially the opposite of "great people" and each have an appropriate type. The Villan merchant, Villan Prophet, Villan Bard etc. Each has the opposite effect on a city than it normally would. Each "barbarian great person" would immediately seek to use their abilites where they could do the most damage. The Villan Merchant would go to the richest country possible, and steal funds (because their bonus would be a - in gold, in most likely the thousands). The Villanous bard would destroy culture, etc.
Tzuross the Lich King.
Appears Mid Game.
Level 3 Lich Summoner. Every Town, Village, Hamlet, or Cottage pillaged by the Lich King, or any unit summoned by the lich king produces a Skeliton in that square - which will also produce skelitons if they pillage. These Skelitons are not considered summons.
Children of the Evermere: Melee Barbarian Unit
Appears Randomly, cannot enter desert, tundra or Ice.
Every time a jungle is cut down there is an X% chance that a Children of the Evermere unit is produced near by. Every time the children of the Evermere destroy a unit, or pillage a tile, it creates a jungle in that tile (destroying all improvements simultaniously)
The Others (Obvious ASoIaF rip off - BUT DAMN COOL!): Magic Barbarian Unit.
Spawned Only In ice and Tundra, appear mid/late game.
Immune To physical Strength and Cold, and are Nonliving. Vulnerable to fire.
0 (or 1) str + large cold damage bonus unit. Whenever an "other" kills a unit that unit is "captured" like an animal and gains the "undead" promotion, and a "vulnerability to fire" promotion. Every square entered by the Others turns one shade cooler - to plains, tundra, or Ice. These should be the baddest bunch in the game

.