To be honest, I have not carried out a comprehensive examination of
server performance. What I can see is that Electrum servers are often
slowed down when a wallet with a large number (thousands) of addresses
shows up, and this is caused by disk seeks (especially on my slow VPS).

Yes that sounds more like what I expected.

In terms of bandwidth, I am referring to my Android version of Electrum.
When it runs on a 3G connection, it sometimes takes up to 1 minute to
synchronize (with a wallet that has hundreds of addresses). However, I
have not checked if this was caused by addresses or block headers.

An address is 160 bits. (1000 * 160) / 8 / 1024 = 19.5 kilobytes of data which 3G should be able to transfer in <1 second easily. Of course the encoding may not be optimal. But if it is, I suspect the issue is elsewhere.