The Paladin 'lull' line of spells is incredibly useful, plus the fact that paladins can root/park adds (or even root/park to pull) coupled with their stuns and hp buffs and gimp healing and LOH make them very valuable to any team not completely hell-bent on min-maxing.
Yay huge sentence.
Both are great tanks, both have nice tricks up their sleeve for keeping aggro, and both kill mobs by waiting for them to die of old age. Classic as can be.
[You must be logged in to view images. Log in or Register.]
Also, SK's don't get all of their class-defining spells early on. Pre-30 a paladin has a lot more utility, although the old adage "you can't outtaunt a SK" is always going to be the case. You'll do well grouping and respecting both classes.