Spain:
Missionary - can convert two cities before being obsolute. Costs +25% more
China:
Cavalry [Rider] - +1 strenght, no terrain movement cost
Mali:
Axeman [Songhaian mercenary? (looks like immortal from CivIII but black] - +1 strenght, 25% desert defence, double movement in desert
Those are interesting choises I think