Partners is not a argument , Tflame and choice scarf/specs Magnezone can clean all Alt's counters too , but i didn't mention them because we are talking the viability of ONE pokemon , not viability of a core.
What I meant to get at more with regards to the partners thing, is that Gyarados usually needs only one partner's help to clean his counters, and having to run Talonflame isn't a huge burden on an offensive team. Magnezone is very useful, but he's being run specifically for something by nature of his niche. The kind of support Gyarados tends to need is stuff that's pretty common to offensive teams already, and with his one consistent set, that broad choice is usually the most Gyarados in particular requires. Altaria tends to call for different support based on its set, which again can play into predicting its set.
Obviously the Pokemon's own effectiveness is the biggest part of its ranking, but how easy/manageable it is to fit into teams or cores can be a factor in viability. For example, Mega Gallade is very effective when played to his fullest, but the team usually needs to be built to support him to get that. Other mons, like Lopunny (to bring her in again), are more splashable because rather than tailor the team to her, you tailor her to the team.
What I'm ultimately intending to get at is that Gyarados's support of "defeat bulky Grass Types" is easier to work in or more likely to naturally be in a team already, while with Altaria, Magnezone is the default (though certainly not the only) support for something walled by Steel Types, and while effective, Magnezone can inhibit team building somewhat because of typing and Scarf reliance. In both cases, the team still is probably built around the Mega, but Gyarados just strikes me as allowing a bit more variety/fitting onto more teams than Altaria.
Also, I think you're underselling something for Gyarados when you note the power difference. Altaria's Pixilate Return is stronger than Gyarados' Crunch, but only because of the Pixilate boost. What this means is that any of Altaria's coverage moves are going to hit for significantly less than Gyarados would. This becomes a problem for Altaria's DD set trying to hit Steel types, especially if their secondary typing mitigates the EQ weakness
(Calcs done with the standard EVs spreads for both, Altaria assumed to have Return and EQ, Gyarados Waterfall and Crunch)
+1 192+ Atk Mega Altaria Earthquake vs. 0 HP / 0 Def Mega Metagross: 214-254 (71 - 84.3%) -- guaranteed 2HKO after Stealth Rock
+1 252 Atk Mold Breaker Mega Gyarados Crunch vs. 0 HP / 0 Def Mega Metagross: 314-372 (104.3 - 123.5%) -- guaranteed OHKO
192+ Atk Pixilate Mega Altaria Return vs. 252 HP / 252+ Def Skarmory: 57-68 (17 - 20.3%) -- possible 6HKO after Stealth Rock and Leftovers recovery
+1 252 Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 252+ Def Skarmory: 127-151 (38 - 45.2%) -- guaranteed 3HKO after Stealth Rock and Leftovers recovery
+1 192+ Atk Mega Altaria Earthquake vs. 252 HP / 88+ Def Ferrothorn: 102-121 (28.9 - 34.3%) -- guaranteed 4HKO after Stealth Rock and Leftovers recovery
+1 252 Atk Mold Breaker Mega Gyarados Crunch vs. 252 HP / 88+ Def Ferrothorn: 151-178 (42.8 - 50.5%) -- 2% chance to 2HKO after Stealth Rock and Leftovers recovery
Altaria's Return hits noticeably harder, but Altaria absolutely needs those Steels weakened/eliminated because it lacks power behind its coverage options. Gyarados appreciates those checks gone, but is capable of muscling past them on its own with some prior damage instead, which I find less to ask of as far as support.
My bottom line is, while both very effective Pokemon in their own right, and deserving of A+, I don't think Mega Altaria any closer to S than Mega Gyarados.