The issue, as I see it, boils down to the following:
Who would be willing/likely to grant a portion of divine power to a neophyte follower?
Right off the bat, we can eliminate evil gods. Evil presumes selfishness (at least to me) - an evil god isn't going to bother pouring his power into an unproven and weak vessel. That is too risky - evil, being selfish wants guarantees - you have to prove your worthiness in advance.
We can also eliminate chaotic gods. They are too capricious, and would tend to grant and take away their favor on a whim. The servant of a chaotic god might do something one day and gain favor - then do the same thing a week later and be ill-favored of the god for it.
Will neutral gods (good/evil or law/chaos axes) do it? Probably not - a thing is what it is, and it disrupts the balance of things to arbitrarily grant it more power.
That leaves us with lawful good. Will a good deity grant his power to a neophyte? I think the answer is yes - because selflessness and trust are characteristics of a good deity. Where the evil deity says, "show me what you can do first, then I will give you the power," a good deity says, "I will grant you the power, and you will be given a chance to show me what you can do." Will a lawful deity grant power to a neophyte? Yes... with certain terms and conditions for you keeping the power.
In addition, when is the best time for a LG god to shape the character of his servant? In the beginning of his career, of course, before habits are developed. A LG god wants to start the training process ASAP. Because of the particular demands of this shaping process, investiture of divine power is almost required so as to allow the character survive long enough to become the paragon of virtue he is expected to become... after all, when your job description entails, "stand toe-to-toe with evil, every time you see it," you'll be put in danger a lot more often than anyone else.
Thus, I can actually see, based on alignment, an argument for HAVING the paladin as a core class. I hope my brief arguments came across.
Basically, the lawful good deity is willing to offer you a trial period with his power, subject to certain conditions, before you prove yourself. The evil deity is not willing to offer you power until you prove yourself, and the chaotic deity is too capricious to do so. The neutral deity simply doesn't want to upset the natural balance by investing his power.
I someone can provide a compelling argument as to why a LG deity would NOT be willing to accept a paladin into service at first level (or why a deity of another alignment would), I'm open to hearing it.
--The Sigil