I should imagine that one of the biggest costs must be bandwidth, in fact only recently i updated both my laptop and computer to Hardy, from Hardy beta, downloading a good 100 of files, twice over.
My idea, (sorry if it's a duplicate,) would be to employ a style of peer-to-peer (like BBC iPlayer *used* to do,) where people could CHOOSE to share the .deb's they've taken from synaptic and act almost as torrent servers.
This would be especially useful in key security updates, for example.
Tom downloads the newest update from Virgin's server.
Nick starts to download the update from the server, but then it is annonced that Tom has it, so he begins to torrent as a suppliment.
After the download a MD5 sum is checked to ensure that Tom's file is pressent and correct.
ideally this would be controlled internally so that from both tom and nick's point of view they're only using update-manager / synaptic.