As i see it, Paladins don't need a deity, but every character should have the option to follow a deity, like you have in Pathfinder games.
Sure. But I'd go a little further and say that unlike optionally picking a deity with other classes, with the paladin class it should work somewhat similar to the cleric class in that IF you pick a deity that deity choice will matter within your class and in how your class works.
