I'd recommend PotD to any RPG veteran even on a first run. The system doesn't make sense on anything lower.
Depends on your mileage I'd say.
You said yourself that without Priest it's much harder. Assuming that someone won't recruit neither Durance nor Grieving Mother, because of their personalities or whatever, and he will have a tough time on first run on POTD (due to lack of helpful CCs), no matter how many times he played IE RTwP rpgs before. Sure, for further playthroughs you can experiment with some wonky parties with success, but for the first run, when you're still grasping the mechanics and usefulness of wiz/pri/ciph spells, you have to more or less have an idea about your party build. First lvls of Priest spells are shit, so there's a lot of chance that someone will dump Durance, even if he consider and recruit him, before he starts to gain full potential.
But then again, it also depends on how fast you learn and you overall ability to quickly grasp the new system - it's doable on POTD, but I'd still recommend for first timers to start on hard.
But those are arguably the two coolest companions, everyone will probably play with them, even if just for the MCA clout.
Aloth is also very strong and probably a staple for everyone, wizards are as OP as ever.
From a first-run perspective, companion-wise, I picked up Aloth, Durance, Kana, Eder, Sagani, in that order (somehow missed Eder at the start... only found him on going back after killing Roedric). At that point, I just didn't feel like swapping the team. Met Grieving Mother next, and was curious about the character and the class, but the party felt too cosy with my dwarf as melee DPS/off-tank, Eder as tank, Sagani as ranged DPS (now cc with Stormcaller), Durance/Kana buffing, and Aloth casting. I have since found all the other characters including the DLC ones, but the way they're scattered, they come in too late for me. I'm sure on a second run I'll do things differently, but the first time, the order and classes does matter a fair bit. I get attached too, as otherwise I may have swapped Eder for Pallegina for example (haven't looked at Paladin in detail, but can't imagine they make bad tanks). Was tempted to kick out Kana for Grieving Mother, but didn't go with it in the end as the chanting felt handy (and no regrets now that he can paralyse, summon Ogres and rez at will). I guess Sagani could have made room for someone else (that barbarian mofo or the Devil of Caroc), but come on, she's a dwarf, I can't kick her out!
As I understand, companions are basically generated at your level (like, just a tiny bit below your current xp). While this is neat, they don't seem to then level up much in Caer Nuad, even from adventures. I realise it'd be a gemey thing to have them magically keep up with the party's xp, but at least I'd have taken them out in turn for a spin (like to take the barbarian to the monastery), whereas as-is, I don't bother: they're too far below
and they would make the main party member they replace miss out on the xp too...
On an update note, Concelhaut tore me a new one. I have conceded defeat for now and left his place to get on with Act 3. I'll go back to try again in a couple levels but I'm not convinced, that's a brutal fight. It's only the second fight I can't deal with (first one being the Alpine Dragon, but at least I got a diplomatic resolution there).