If you are questing and killing mobs one or two at a time, I might spec the paladin retribution and the priest shadow.

If you are aoe grinding, I might spec the paladin protection and the priest holy/disc. Note: this one is nice since you can run 5 man dungeons with friends, PuGs and have the critical two spots in the group covered.

All that said, I would sincerely suggest spec'ing them in a few different combinations (prot + holy, ret + shadow, etc.) and play that combo for a level or two just to see if it fits your playstyle.

The best spec is the one that you have the most fun playing.