If you want to go way back to the Captain Eddie days, they were "The Great Silver Fleet". "The Wings of Man" slogan came out shortly after EAL's 1965 makeover (the birth of the "hockey stick") as the last vestiges of the Captain Eddie era were being thrown out.
In the late '70s, EAL introduced a new slogan "We Have To Earn Our Wings Every Day". Along with it came a series of commercials featuring Frank Borman. That one lasted until the mid '80s (immediately pre-Lorenzo) when it was replaced with "America's Favorite Way To Fly".
EAL went through a series of slogans during the Lorenzo era. Right now I'm looking at EAL's last timetable (dated 1/1/91) and I can't find any kind of slogan in it.
Sadly, toward the end of EAL, another slogan began to circulate among the employees. BOHICA.