since every peer has to receive every transactions eventually, it seems that Transactions * Peers is the absolute
minimum of transaction sends you'd need. Am I missing something trivial here?

As far as I understand, a peer will send every transaction to everyone he hasn't received it from. So this results in an additional multiplicative factor of something like k/2, where k is the average number of neighbours for a node. (Or is it much more than that?)

Is it this factor that you'd like to get rid of, gmaxwell?