Conclusion: Ali over Mike decisively. It's practically even a joke that we're having this discussion when the facts are laid out like this. Ali beating Foreman puts him to greatest of all time status because Foreman's accomplishments are so astounding. Mike wouldn't have even beaten Foreman, let alone Ali. Ali and Foreman both took huge punches that would have KO'd Mike (and did). For Ali, see the Shavers fight. For Foreman, see the Holyfield fight where Foreman withstood the same direct blows that KO'd Mike.
Most exciting fighter of their respective day would be a tie between the two. And Mike indeed was the most strikingly exciting fighter of his generation albeit amongst a (at times) fairly lackluster field. I do believe some people confuse excitement with greatness. Yet, I still find Ali's fights more enjoyable and competitive.
Shavers is another example of someone who punched as hard as Tyson, and probably would have beaten him.
Anyway, if Tyson was so great, he wouldn't have avoided fights with Riddick Bowe and Foreman. Especially the fight with Foreman would have netted the biggest heavyweight payday of the early 1990s.
Ali's greatness was fully realized compared to Tyson. Ali fought and beat all of that generation's greatest and hardest punchers: George Foreman, Kenny Norton, Joe Frazier, Larry Holmes, Sonny Liston, Earnie Shavers, Leon Spinks and Floyd Patterson, who was also Cus D'Amato trained.