I am thinking about a different strategy for this: OCC + PA and play GPFarm for my ally.
EDIT: All my comments refer to Vanilla/Warlords OCC + PA, unless qualified as BTS.
It will be extremely hard to get a cultural win via OCC + PA at Deity level.
Getting the PA will require mutual war or DP (Military Tradition), followed
by either Communism or Facism to allow the Permanent Alliance.
A date less than 1800 AD will be extremely difficult via OCC + PA
and the top dates for this gauntlet will likely be < 1300 AD.
1: Which AIs are good at getting an early cultural victory?
The AIs in BTS actually try to win via Cultural Victory, so start there.
My experience with OCC + PA is in Warlords which is similar to Vanilla.
Your PA partner will do nothing to increase culture in his two highest culture
cities, until somewhat close to a cultural win. The situation in BTS should
be much better.
Ramesses II will build many WWs early on. Research the tech that unlocks
the WW you want him to build and gift it to him on the turn you research it.
This is advice for Vanilla/Warlords. There may be better choices for BTS.
I played a test game with Asoka as my PA, and I couldn't get him to touch the slider or spread his religions around at all.
Not sure there is a way to force your PA partner to increase the culture
slider. There may be a way to do this in BTS.
If you and your PA partner have about %50 Pop, build or have him build
the UN, and vote for Free Speech.
Gifting missionaries to your PA partner should work somewhat OK in getting
him to spread his (your) religions
Will the AI recognise that my city will become Legendary, and so only focus on two culture cities?
In Vanilla/Warlords this seems to happen, mainly by accident, but only when
a cultural win is only a few turns (10-20) away.
In BTS, where the AIs may have the goal of a cultural win very early in the
game, this may happen earlier than anyone suspects.
If I gift the GAs instead of settling them, will my PA culture bomb them in those two cities, or waste them on golden ages and such?
In Vanilla/Warlords, gifted GAs are bombed in only culturally weak cities near
your capital's high culture. Otherwise, the GAs are used/saved by your PA
partner for golden ages.
2: Which AIs are easy to get in an early PA?
Ramesses II will enter into an early DP. Do almost anything to make him
pleased and he will be ready to enter a PA when it is available.
3: Which map settings make it easiest to get gold or gems at the start? I am all for using MapFinder, but I don't want to run 7000 regenerations to get a good start.
To reduce the number of cities your PA partner has and thus reduce the
number of WWs and other culture wasted, select the maximum # of
opponents (7 for Small). If you are somewhat lucky, he will be land locked
in two cities. Terra map may be best here. (The downside is fewer
potential Cathedrals due to only 2-3 temples per religion.)
For gems at start, Pan and Terra are good.
For golds at start, Inland Sea and Rain forests (BTS only) are good.
Good luck!
Sun Tzu Wu