How could block propagation time be reduced?
Gavin Andresen wrote a bit on the topic here: O(1) Block Propagation.

Essentially, he is implementing the conclusion from your answer, a way to get around resending all transactions when propagating a new block. He is working on implementing Invertible Bloom Lookup Tables to use for set reconciliation. IBLT excel at comparing sets of significant overlap, and therefore are very efficient at relaying the differences between included transactions and Mempool of recipient.