Trash between Halfus and Valiona
Keep in mind that as you go through the gates and down the stairs, you are running a gauntlet. Every so often, Cho'gall will send an elemental up the stairs as you pull the adds. We have one tank picking up the adds and holding them up the stairs a bit while the second tank taunts and eats the hit from the elementals. The shadow elemental leaves a debuff on you but the fire elemental hits kind-of hard but more worryingly, knocks you back. Make sure you're getting hit straight on with your back up the stairs or you can find yourself flung off to the side into lava with no way out.
Alternately, you can have ranged DPS swap and kill the adds but... it's not as much fun and you don't get to fly. Wheee! :-)
When you get down to the platform below, you can just split the pulls between two tanks on all the ogre and dragonkin groups, but the elemental groups can hurt a bit. CC as much as you can and nuke down the fire elemental first - he does massive amounts of AoE damage. Once he goes down, you can get gather 'em up and AoE.
(Edit: As Marilee mentioned in the comments, if you keep the humanoids CC'd the fire and earth elementals don't seem to cast their big AoE's and you don't have to quite so frantic about burning down the adds.)
Valiona and Theralion
1 tank, 3 healers
I hated the Valiona encounter in Heroic Grim Batol but now I kind of like it. This fight is similar in many ways. It's a two-phase fight with two very short transition phases and you keep repeating them, so once you see both phases you've seen the whole fight.
When Valiona is on the ground, you want to be close to spread around her. Designate one person to group up on (we use our Resto shammy standing under Valiona's butt surrounded by his totems) to gather for Blackout. Also make sure you designate only one healer to make the call for when to cleanse Blackout off the afflicted person and to cleanse it off - an early cleanse will kill that person and anyone close to them. No other healers should touch that cleanse button. This is vital. Hammer it into your healers who will see a debuff and auto-click cleanse and kill the poor victim.
Occasionally Valiona will spin to face someone, rear up her head and then do a 180-degree breath attack just like in Grim Batol. Run behind her and when she spins back to the tank, spread out again.
Dazzling Destruction will hit just before she takes off during the transition - remind your raid this is not a DPS race and they should just run away and not try to get that last lick in.
If anyone does get sucked into Shadow Zone tell them to heal themselves if they can, avoid the little white mines floating above the ground and to make their way to one of the portals and click it to get back to reality. But really, there is no reason to get hit.
Theralion is a bit more complicated - we split up our raid in two groups of five and five. Melee and tank in one group and any spare slots are occupied by healers first. The second group is composed of all the ranged and at least one healer who's good at cast'n'run (we put our shammy in the melee clump and the druids at ranged.) Designate one person in the ranged clump to be the collapse point.
Valiona shoots meteors that need to be split among people, which is why you have two groups, but Theralion will also put bad stuff under people's feet so you want a group at ranged to draw those out, as black puddles on the tank is bad. Just keep the boss in the middle of the room and have the ranged group move in one direction as the shadow puddles drop.
Occasionally, Theralion will buff/debuff someone with Engulfing Magic which is exactly like it worked on Heroic Sindrigosa - have that person run out of the group they're in and when they're safely far away, let them go crazy with their nukes as they will have a 100% buff to damage (or healing) but will damage people around them. Thus the running out.
The transition from Theralion to Valiona involves an Onyxia type deep breath that goes in horizontal lines across the room from one end to the other - just watch where she is lining up (we call three zones - Near, where we came in from, Middle, and Far for the strip in front of the, uh, far door.) and call it out. You have plenty of time to get out of there and move to an adjoining area. Getting trapped by breath will also port you to the Shadow Zone and you get out through the portals - same deal.
We hit Heroism in the Theralion phase when our Fire Mage or Hunter has the Engulfing Magic buff for big numbers. Remember DoT classes can keep DoTs up on both mobs and since they share health pools, it just helps speed the fight along. But this isn't necessary, really, just speeds things up once you get the hang of it.
After that, Valiona lands, and it's back to her phase and repeat till you wipe or they die. You only need one tank for this so swap to Retribution if you aren't tanking and get ready to Templar's Verdict your face off. This might seem really overwhelming at first, but really it's just knowing when to group up and spread out - a couple of pulls and it will become really easy and predictable.
The biggest sources of problems are when people get hit by the deep breath or dazzling destruction, or when Blackout gets cleansed early. Also, when people get targetted for Meteor during the Theralion phase, they think they got targeted for Engulfing Magic, run screaming from their group, get hit for 300k by the meteor and die leaving a bloody burning splat behind.
Just take a look at your debuff before you run - you won't damage people unless you're casting and you can control that by, er, not casting.
Take a breath! Relax. It's going to be okay.