Yes, run.

I've tried healing through this with my priest and it is ROUGH. I don't know if it's just easier to time this with shamans or what, but I had about a 25% chance of success healing through it.

With Paladins it will be different, but with my group the way I do it is line my guys up in a position where they have room to the left (or right, whatever you prefer) to strafe. Once he begins channeling his explosion everyone strafes out of range. The only tricky part is getting them lined up again so that during the next explosion you have room to get out of range again. I usually only have to avoid 2 explosions, maybe 3.

Once you've got the timing down and know where you're strafing to, it's not too tough.