Churchill/Zulu: Nothing special if you aren't a warmonger, tough nut to crack if you need him out of the game quickly.
Victoria/India: An early warmonger's paradise. Great for worker stealin'
Elizabeth/Dutch or Portugese (an attempt at "honor harrington"): Attempted to truly make a respectable naval power out of an AI. Just doesn't work. Navies can be important, but Civ is more about the land, and no UU really deal with "big ships blowing each other up a lot".
Genghis Kahn/Korea or Russia (mongolian expansionism): Nothing special I'm guessing with Genghis, the only civ combo that might get him to really become an early era terror is Inca
Kublai Kahn/China (Kublai's claim to fame, sticking it to china): Now this one gets a little more interesting when you give Kublai a civ that synergizes better with his creativity. However, the only time I've seen real impressiveness is when genghis/Mongolia is team-linked with Kublai/China.
Hatshepsut/Maya: When I saw the city "Debra Bernham", I was like, Hey, that sounds like a name for a fake leader....so I tried this. Again, nothing special should you want to war against her, but Hat/Maya will beat Hat/egypt most days in isolation to a culture victory.
Tokugawa/Korea (when the japanese weren't warring with China, they were conquering (or trying to conquer) Korea: Since Tokes is AGG/PRO, find him a civ with a UU that actually gets promotions should he build it, perhaps, but korea was nothing special for Tokes.
Lincoln/Celts (based on a fictional character named "ballard"): Dunno if Lincoln is programmed to rush rifling, but he had them fairly quickly once on a fractal map. Doubt the programmers were this good, but most of his land was very hilly, so that would have been a very tought nut to crack
Brennus/America: Starting in ancient times, well, since America's UU and UB are both late game which is talked about, I'm guessing that with a military AI personality, this is one of the worst mixes to give an AI....Never did well in any games I in which I watched him slog along.
Frederick/Holy Rome: This one is actually a better fit for Frederick than Germany, but even so it really doesn't augment Frederick's personality much.
Celtic Leaders of France: The gauls were celts, right? Didn't seem to make much of a change. as has been pointed out by many before me, the celt UU adn UB shine based on odds of terrain, and typically the odds are not kind to the AI. So France, with a slightly better UB, (But the AI rarely uses 2-move units to their best advantage unless in pillage-harassment-mode), and nothing Bootycall can use for an interesting UU, doesn't seem to make much of a difference.
Ragnar/Celts. The vikings seriously DID culture spawn both in London and Ireland, right? (heck, the English have a dynasty of Danish Kings.) Even though it has been debated that the programmers have improved AI amphibious assaults from earlier versions of civilization, it is argued it still leaves a lot to be desired, so most of the time the UU is wasted on the AI ragnar. If Ragnar is playing in a DEFENSIVE posture (which sadly he's forced to with his weak start on earth maps, specifically 1000AD) giving him the celt civ on hilly terrain is useful. However, in the end, the loss of the UB of the vikings to trade for the stuff of the celts only helps ragnar if his civilization is again mostly inland on rocky terrain.
Isabella/Portugal. It must have just been a fluke, because random personalities weren't on, but giving isabella 2 civs teamed together one Izzy/spain, and one Izzy/portugal, the portugese was hugely expansive. It was like even though izzy wasn't ever MEANT to channel Joao, but she had. Its interesting that Izzy seems to be programmed to win by teching/spreading religion and more cultural-economic means, but her UU/UB combos of spain are more bent on military conquests. So I think Izzy of Portugal, if she DOES REX more, seems to fit her AI personality better. Though why that happened in the one game I observed is beyond me.
Pacal/Inca: Only did this one on an unmodified AD1000 map. I think to get out of that chilean hell, would take either Portugal or some expansive leader that is programmed to prefer sailing. No hope there.
I think in the end perhaps for an open random map any agressive leader would be best teamed with the incan civ. (they are going to spam warrior types, right? put that combat 1 promo to use and maybe give them a UU that they can become very scary in early war.)
Late game?: Since Elizabeth's personality seems to be programmed to tech well to a late game, and defend herself better than gandhi, I'd claim maybe Elizabeth could mix with America. Even though the Navy seal is a sucky UU, it's mostly because it appears late in the game, not because of it's very limited use, such as the Panzer. I can't think of any other late game unique-blooming civ other than america and Germany at the moment