Altaria has a lot of potential, but IMO, having just 10 more base offenses would have been awesome. It's usable in UU, but the lack of firepower is disheartening. What could the new move be? Maybe a song-based attack? Then again, it already gets Sing, and not very many other sound moves makes sense on it.
Now that I think about it, Altaria could have checked Excadrill if it didn't need a scarf to outspeed it or actually had the offenses to kill it (I think Fire Blast might OHKO, but not sure).