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?
On average each node should receive each transaction once and send it onward once. Better connected nodes would tend to have more peers who haven't seen the transaction and so request it.
That is where the suggestion to pick 2 nodes to forward it to comes from. If each node immediately sends it to 2 others, pretty soon the whole network knows about the transaction. It doesn't matter how many you are connected to, you only really need to forward it to 2.
The more efficient method could be used later to catch detect peers who didn't get it.