Before we talk about what shoes AE had with her on the world flight let's focus on what Gallagher said about what he found.
Why did he think it was a woman's shoe?
What made him think it was from a stoutish walking shoe or heavy sandal rather than some other kind of shoe?
Stoutish walking shoes and heavy sandals don't have high heels, so that's not why he thought it was a woman's shoe. We've already reasoned that the part-of-a-sole that Gallagher found was probably rubber, but both men's and women's shoes can have rubber soles, so that's not the answer. Karen Hoy hit on one possibility. What if the part-of-a-sole that Gallagher found was white or cream colored? In 1937, a white or cream colored sole was almost certainly from a woman's shoe.
Stoutish walking shoes and sandals with rubber soles have the heel molded in as part of the sole rather than a nailed-on heel as in regular shoes. It seems to me that Gallagher's description makes sense if what he saw was part of a white or cream colored rubber sole with the heel molded in rather than nailed on. Anyone have a better idea?