Pallies have better initial threat and single-target threat, after 15 secs it really doesn't matter all tanks are equally good (pallies actually are probably the worst at sustained threat over long fights).

All things being equal, a DK is slightly superior to a pally tank right now imo. And I run a pally tank, mage, resto shaman, and 2 ele shaman group that has cleared every heroic almost (oculus/HoS not done). You will do fine with a pally tank too, and in the future you can dual spec talent him as holy or ret for solo play, whereas DKs are pretty much only tank/DPS (but very high DPS!).

It takes only ~20-30 hours to level a DK from 55 to 70, so imo if you are just starting out I'd go with a DK, since by the time either hit 80 they will be geared the same.