I would think the best race to be a Half-Celestial/Half-Human or Half-Dragon/Half-Human. I also don't alow my players to play as anything from the MMs that's not a template and not alive, unless there previous PC died and there making a Ghost or Dark Knight of that particular character.
I think you're going to have to create a race if you want a +0 LA paladin race. As far as I've inferred, the point of the paladin is that humans are supposed to be (by design stanards) the best basic race for the job.