I'm gonna dual log a holydin, mostly because for the really hard stuff, you want a real healer(elite quests and stuff), and a healer lets you AE more mobs which makes leveling faster too. Paladin is a pretty solid choice because they provide BoM which is probably one of the biggest dps increase a DK can get, crusader aura for travelling saving you 2points from Pale Horse, an almost all purpose dispel for all these annoying debuffs, the biggest single target helaing output even when not paying much attention and it works fine in PvP too since you can't just bubble the paladin to ensure a period of heal spam, and dispel any CCs/give freedom for snares/roots.

They're not very good for DPS obviously, but you can at least macro Holy Shock linked to all your DK strikes, so you'll shoot it every 6secs(if you can maintain it on mana, unsure), it's not great but the support aspect is good enough, and you can use an addon to autorefresh seals when they're down, and judge too. Another good choice is shaman, with stuff like bloodlust and windfury, and the fact you can easily add DPS by using lighting bolts/chain lightings and shocks. I didn't like some aspects of it however, so I'm going paladin myself. Priest and Druid I guess are also decent, but they offer the least in terms of support, and all the group healing tools are close to worthless when dual logging.

I think adding a DPS is not very useful, you're not gonna level any faster with a DPS and a DK because DKs are leveling machines, so they're already at the top of the food chain for solo leveling. Adding a DPS, even assuming you can get 100% out of it(BM hunter for example), will still be much slower than simply soloing, and it won't open a lot more content because even blood speced, a DK can have issue against some elites, especially before level cap and good gear.