While leveling, a pally could technically be better in this situation so you can get to 100% pushback resistance with concentration aura if you’re specing destruction. A priest is overall the stronger healer currently though if they want to level a priest.
At 40 if you went soul link, a priest’s PoM is one of the strongest and most mana efficient heals in the game and could bounce back and forth between you and your pet. A pally could beacon heal you both at the same time though.
At some point the priest can get power infusion which might be a nice cooldown to pop on you on a big pull.
Pain suppression might be nice at some point, though a paladin could BoP you and shield themselves in some situations which would be stronger I guess.
Blessing of Sacrifice on you and beacon of light to heal you both at once might be an interesting combo someday, but that’s level 46+.
Resto Shaman if you were Horde would be more annoying to keep ES up for pushback resistance (we’ve been asking for buffs to ES since phase 1 though so maybe we’ll get them this phase), but downtime would be lower as they could pant swap to Shamanistic Rage with DW rockbiter to reduce downtime between pulls.
Probably just have them pick whichever healer they think they’ll enjoy more at 40. Pallies and Shaman are more likely to get buffs at some point since priest’s are currently on top. 
Resto Druid and Mage healer could honestly be options as well. You’ll have a lot more AoE with a Mage secondary to kill faster, though not sure healing wise how it would work since their AoE beacon healing is severely nerfed. Resto Druid also seems fairly likely to get buffs to underused runes like lifebloom and seed at some point… though they ignored them throughout phase 1 so maybe not.
edit:
I guess I could also mention I did a decent chunk of leveling to 40 2 manning SM Lib/Arm/Cath myself, but I did it as a resto shaman with a feral druid. We didn’t AoE, just pulled one group at a time. I tanked and healed myself while the feral shredded things.
If you took a less AoE and slower approach you could also do lock + shadow priest or lock + mage or lock + druid spamming wrath (balance or resto) or lock + ret. They’d be able to heal you enough as a DPS while adding more damage.