The arena starts at level 9, and will go most of the way, I think. XP-requiring spells are banned, as are certain game-breakers. Also, there's no incorporeality, slightly devaluing those templates.
Design Principles:
I have become convinced that arena-appropriate power in gestalt is gained through breaking some mechanic. (I can talk freely about breakage - it's an arena, after all.)
Full spellcasting is obviously near broken normally. In gestalt you can be tempted to gish (which you can't otherwise), or dual spellcast. I think both of those are weaker options than just making the full spellcasting rather irresistible. Sorc + Paladin is good. Sorc + Pixie/Gravetouched Ghoul/Evolved 14 for +36 Charisma is better. Immensely better. Even a splash of paladin for Divine Grace isn't obviously better than taking a spell that does it for me, because the spell version gives me +2 saves (and +2 DCs and so on). I can get Cha to just about anything I want by some feats, equipment and spells.
...so I'm thinking about trying to max out charisma using one side of the gestalt. Another casting stat would work about as well, but I suspect Charisma is easiest to max. Plus, it helps out with the odd SLA generated by LA.
So... Sorc 20 (or equivalent) plus,
Pixie/Gravetouched Ghoul/Evolved = +36 Charisma, undead, small (in the late game) other benefits
Nixie/Gravetouched Ghoul/Evolved = +40 Charisma, undead, smaller other benefits.
Succubus/?? = +16 Charisma and 8 free LA.
Can you do better than that?
I can take racial HD advancement on anything, but that's not immensely strong even on a dragonwrought kobold, who gets: +1 BAB, good saves, +1 NA, +1/6 mental stats, +1/3 str&con, and +2/3 sorcerer casting level. It's good, but not immensely strong because it's hard to generate gestalt-level save DCs with only +9 Charisma at level 18, so that huge caster level is hard to utilise. A maximised 34d6 wings of flurry is still zero damage if they make the save (everyone'll have evasion somehow).