Interesting question. Myself, I think Lay on Hands progression, Smite Progression, and Mount Progression are all pretty close to as important as spellcasting progression for paladins--possibly more important.
I think your answer to the first question is right: you gain one paladin spellcasting level every two levels. (Note that this really means you only gain an increase in spellcasting ability every four levels).
To answer your second question, taking several levels of cleric (if you took 2 levels of cleric, you'd lose one point of BAB but end up with 4th level cleric spells instead of 2nd or 3rd level paladin spells) might help but it won't solve the underlying problem. The underlying problem is that the Shining Blade of Heironeous is a rather pathetic prestige class. Paladins get very little (wohoo, a couple of times per day, I can spend a standard action in the first round of combat to get an enhancement for my weapon that I'd probably get anyway). And they lose the features that enable paladins to really shine at high levels: lay on hands (at high levels, sometimes better than a Heal spell), smites (especially in conjunction with power attack and spirited charge), and mount progression (see previous note on spirited charge). They also lose a LOT of what little spell ability they have.
As for the best class combo for Shining Blade of Heironeous, it's probably Fighter/Cleric. Over ten levels, the class gains two points of BAB and a few hit points vis a vis a Ftr 5/Clr 5 as well as the flavor-text blade abilities. (Brilliant Energy is really the only one that's interesting and it's only interesting becaue Brilliant Energy is such an odd enhancement--enough to decide an encounter against a PC or NPC who will usually get hit on most attacks even with max power attack from a brillian energy weapon but useless against a lot of "monsters" and counterproductive against undead and constructs. (The last bit means that most characters probably don't want their primary weapon to be brilliant energy because that would force them to go to a backup weapon vs. undead and constructs)). However, when considering this, you need to keep in mind that even multiclassing is about the dumbest possible way to construct a multiclass character. A Fighter 8/Cleric 12 is undeniably better than a fighter 10/cleric 10 (6th level spells and +1 to will saves are more than worth 2 hp and a bonus feat) and Fighter 4/Cleric 16 is probably even better. Fighter 4/Cleric 6/Shining Blade 10 (or better yet, Fighter 4/Cleric 4/Shining Blade 10/Other p-class 2) is better than Fighter 10/Cleric 10, and is possibly better than fighter 8/cleric 12, but I don't think it competes with fighter 4/cleric 16 very well. And of course, that's only thinking of core multiclasses. Compared to other prestige classes (for instance, Hospitaller or Warpriest), it's just plain bad.
