One more leader that needs another look at with regard to the UU is Spain.
The Conquistador that can act as a missionary was a good idea in theory, however in practice it was worse than useless as the "Unwelcome Evangelist" attribute used to enable missionary activity meant it died in the field before it could be used as an offensive unit. This ability has been removed now and it is just the vanilla unit again.
I have never found the vanilla ability of settling new cities on other continents very effective, why build an expensive military unit that may soon become a city?
Perhaps give the unit something like the "Heathen Conversion" ability that converts barbarians to the 'way'?