Deathwing is a difficult villain to make interesting to players because his beef has mostly been with the other dragonflights historically and he's just such a big, cosmic kind of enemy that you get a little detached from emotionally investing in him. He's more like a natural disaster as an antagonist (like you know, the tornadoes in Twister etc.), than a real entity. A problem, but not a very personal one.
Arthas/LK was handled pretty badly in WLK (and WoW in general) by being so detached and passive and just not very scary most of the time, not doing much with the power at his fingertips unlike WC3 where he was really freaky and made a lot of trouble. But conceptually, LK is a much better villain because he's a real personality, he exists on a personal level — the things he does have real bite and malice and they directly affect everyone in a very aggressive way. You are fighting against an evil person who does really evil things rather than a detached destructive force with a bunch of admittedly evil minions.
Some people just like having a villain who's big, intimidating, scary, and actually does things. On that level, within the context of WoW, I can see why Deathwing is more appealing or at least refreshing after LK basically sat on his sofa and munched Pringles while concocting a ludicrously contrived trap for the players, the whole last xpac.