In the pic above (from the top down), that's the 1972, '75, and '80 Mr. Olympia lineup. I think the "Arnold had small legs" thing only comes from looking through a different perspective. I'd say they appear at least on par, if not better than a few, compared to his competition.
But like Stu said, the criteria back in the day was way different than in the modern sport. I do think it was a whiny and misguided cheap shot by Health, no doubt.
FWIW, this is that Bloomberg interview Phil mentioned doing this past October. He did seem to present himself professionally, even if the lady did lump bodybuilding in with "Tough Mudder, BMX, and things like that."