Cartmanbeck,
Your idea is creative and has merit, but the scouting ability has been very helpful in the 4-6 player games I've played with the paladin. I do like the shield bash to alleviate the frustration of not starting with a weapon in hand, but if I had to choose, I'd take the scouting ability. I think it can really accelerate exploration.
Fromper,
Limited sample size for me...half dozen games with 4-6 players with most of the characters in the mix (not seen cleric played), I don't see the paladin as underpowered at all. Good explorer, good combat, solid at any check with the d6 bonus, some healing in a pinch. Maybe I'll change my tune as we play more, but I don't see what you see thus far