tl;dr: Ragnaros the Firelord is the best consistent value. He helps build decks for at least paladin, warrior, and mage. Ragnaros, Lightlord is probably the best if your friend has decks for other classes or really specifically wants to play paladin.

Cairne Bloodhoof is used in a few decks right now, because it's one of the strongest sticky minions when there's no Naxx or GvG. He might fall out of favor if N'Zoth doesn't remain in the meta or if better deathrattles or 6 mana minions come out.

Ragnaros, Lightlord is strong now against aggression. He heals for 8, and (if your opponent doesn't immediately have lethal after that heal) he eats another 8 damage, a silence, or a hard removal. He also threatens a lot of damage himself. He is only useful for paladin though, and he isn't a classic card.

Ragnaros the Firelord has basically always been a good card. This recent ranking list put only the Firelord and Sylvanas as top tier legendary minions.

I'd choose the Firelord. N'Zoth Paladin, Tempo Warrior, some Control Warriors, Tempo Mage, Reno Mage, and others run Ragnaros the Firelord right now. He's a pretty decent substitute in other midrange or slow decks if you don't have the dust to craft all of the legendaries and want a big threat. He's a classic card that has basically always been at least good if not great.

If your friend really wants the playstyle of a slower control paladin, has good mage and warrior decks, and doesn't need a good late-game threat for other classes, then Ragnaros, Lightlord is probably the most important legendary for N'Zoth Paladin specifically. There are a lot of aggressive decks out there, and you need to have ways to recover health if you survive the early game. Cairne and Firelord can be replaced with inferior cards for that deck specifically, but there aren't many heals in the game right now.