Mega Altaria terrorizes Stall and Balance, but Offense tends to either A) not give it any set-up opportunities or B) revenge it fairly easily after it's set up, since 75/110/105 defenses aren't THAT bulky and it's sitting at only base 80 Speed. I play offense fairly exclusively (we don't talk about that time I used a BW1 rain stall team), and it's never been that big of an issue for me. Nidoqueen especially handles it well. It has to set up in order to OHKO more offensive Nidoqueen spreads, all while Sludge Wave OHKOs after Mega evolving and Ice Beam always OHKOs if regular Altaria switches in on Rocks.
252+ SpA Life Orb Sheer Force Nidoqueen Ice Beam vs. 0 HP / 0 SpD Altaria: 489-577 (168 - 198.2%) -- guaranteed OHKO
252+ SpA Life Orb Sheer Force Nidoqueen Sludge Wave vs. 0 HP / 0 SpD Mega Altaria: 385-455 (132.3 - 156.3%) -- guaranteed OHKO
252+ SpA Life Orb Sheer Force Nidoqueen Ice Beam vs. 0 HP / 0 SpD Mega Altaria: 244-289 (83.8 - 99.3%) -- guaranteed 2HKO
252+ Atk Mega Altaria Earthquake vs. 128 HP / 0 Def Nidoqueen: 240-284 (67.9 - 80.4%) -- guaranteed 2HKO
Mind, you can also go for max physical bulk and live a +1 Mega Altaria Earthquake and retaliate with Sludge Wave. So maybe Balance also has a shot.
8 SpA Life Orb Sheer Force Nidoqueen Sludge Wave vs. 0 HP / 0 SpD Altaria: 265-315 (91 - 108.2%) -- 50% chance to OHKO
+1 252+ Atk Altaria Earthquake vs. 248 HP / 252+ Def Nidoqueen: 252-298 (65.7 - 77.8%) -- guaranteed 2HKO
Mega Aggron also stops Altaria cold, but I've only ever used it once on a fairly unsuccessful team.
EDIT: Of course, as soon as I post, I remember Dugtrio. Unfortunately for Nidoqueen, CB Dugtrio DOES handle it very well. Unfortunately for Dugtrio, Mega Aggron is barely 3HKO'd without max Defense investment, whereas you have a 30% chance to 3HKO WITH max investment. Choice Specs Magneton can KO with Thunderbolt with a little prior damage, but now you've devoted two slots to taking care of Altaria's two most prominent counters.
Neither of them have reliable recovery, but I just don't feel like Mega Altaria is that good. I think it got a little overhyped like Mega Absol. Even with Pixilate, 110 offenses doesn't seem to scream "top-tier threat" to me.
Keep in mind this is all taking Altaria as an offensive threat. I haven't seen it used defensively yet, so I don't know what to make of it, but that typing is pretty sweet.