Firstly, I'm assuming you're doing 3.5 since you said ACF instead of archetype?
Paladin is one of the stronger passive classes in gestalt. Ideally it would only be taken for two levels to get Divine Grace, but it's still a d10, full BAB, good fort save and has a scaling special mount. Any charisma based full caster (just Sorcerer and the much weaker Shugenja as far as I can recall are pure charisma, with several classes being MAD dependent upon charisma) is a potent combo on its own. The biggest strength you have is that while gestalt is typically simplified to two halves of a character, the actual rules say you combine two classes. This is actually to your advantage as a Paladin since, under that wording, Battle Blessing (Complete Champion) applies to spells from both halves as your one class that is named "Paladin".
If your GM doesn't bite on this, I note Shugenja is actually quite a bit better than normal under these circumstances since you get the proficiencies of Paladin, and its Turn Undead (which Shugenja desperately wants to qualify for prestige classes that expand its lackluster spell list). Sorcerer is still likely better (especially since shugenja are spontaneous and therefore unable to use Swift Spell and abuse Ruby Knight Vindicator even if it isn't barred from gestalt and deity restrictions), but it's absolutely an option.