Separate data and engine packages, engine package distributed by Debian, data left as the responsibility of the user. That way the iD games are in debian too.
It could be packaged, without assets, but with an "installer" that prompts for a cd/source to copy from (along the lines of what ttf-mscorefonts-installer does, for instance -- or freecraft[1] for a more similar example: "FreeCraft needs a lot of data (maps and artwork), that can come from WarCraft II CD, or from the FreeCraft Media Project, codename fcmp, that has support for almost all the data present in WarCraft II. (...) WarCraft II is a registered trademark of Blizzard Entertainment.").
