Not on flights, but sitting in airports:

Evander Holyfield at ATL - walking down the concourse in sweats carrying a duffel bag. Man, that guy does not have an OUNCE of body fat. To make sure it was him, I discretely checked out his ear - it was after the Tyson fight.

James Takai (Star Trek's Mr. Sulu) in the DEN RCC. Once again, how to confirm it was him? He turned and spoke to a friend - ah, that deep voice... yep, that's him.

Joe Montana in the DFW Admiral's Club. Very polite - he gave me an autograph for my wife (the die-hard 49er fan).