I'm also firmly in the camp of wanting my paladin to be able to have a deity. But I agree completely with the broader point of any custom PC being able to pick a deity, and to have some dialogue and world reactivity from their choice. Choice of deity ought to be treated just like any other demographic choice in the game such as race or background.
