Dunno about the leaf, but the notion that the fruit of the Tree of Knowledge of Good and Evil was an apple is relatively recent. I believe that pomegranate was an early candidate. I'm researching the fig leaf thing. Be back later.

Oh, and in a related story, I prefer "fruit flies like an apple" to "fruit flies like a banana." It better matches the "time flies like an arrow" part of the pair.