|Multiple Packages.gz files does address the issue of being able to exclude large groups of software. I would be surprised if the average workstation didn’t have software installed from 80% of the categories anyway. What exactly would we be giaining here?
Another, more complicated answer would be to employ a versioned Packages.gz file. Generating the necessary patch files could be stored in a filesystem layout based on the version number. For example, apt would request the Packages.diff.gz file from the directory of its /current/ version (i.e. ftp://ftp.site.tld/debian/dists/woody/i386/main/Packages/20020405001/Packages.diff.gz)
CVS would not be required for such a system, since the client only needs to know its current file version. The server can generate patches either per request through a scripted backend, or manually as static files (depending on how you want to manage your disc space and how complicated you want to make things.) If the patch exceeds a given percentage of the total size of the Packages.gz file (which may actually be symbolically linked to ./version/Packages.gz), the patch could be excluded, and apt would download the new Packages.gz file in its entirety. The downside of this is the increased maintenance of patch and diff files and ensuring that synchronization is silmultaneous for all patches and new versions of the source file.
This solution does not address the issue of downloading package descriptions about software you have no interest in. If this was the desired goal of apt clients, then an apt server application would need to be developed so that the client could selectively query about packages instead of relying upon locally cached databases (Packages.gz). Such a setup would migrate away from the KISS philosophy that much of the Debian packaging system embraces.