The smallest is Debris. There is no other known distro with Gnome & Debian with less than approx 640MB.
Go to the above page and forum, you will find people doing bootable dist and backups of Debian and Ubuntu systems.
It is very easy to make your installed system a bootable live-cd or live-dvd with Remastersys, really, i've already done, 30 minutes to put my 3.5GB Debian Gnome in 1.2GB live-dvd.
Install the Debian Testing iso cd-1 only and make it the way you want. Then, Remastersys.
-Debian Live Project (http://debian-live.alioth.debian.org/
Maybe you can strip down a Debian live cd of Lxde (481MB) or Gnome (+700MB) and make your own flavour. See the Download section.
An easy to use Openbox distro based on Ubuntu. The design is a must, doesn't need to be changed. (crunchbang-lite-8.10.02.i386.iso 448MB)
Excellent distro and the fastest installer I've ever saw. Only KDE or Xfce versions, but you can make your own Gnome version starting from Xfce because it is smaller and Xfce is very compatible with Gnome.
Download the Xfce version, install on hdd, install the Debian Lenny kernel, install Gnome, install Remastersys and make your live cd.
(sidux-2008-04-xfce-i386.iso 385MB) new with 2.6.27 kernel
(sidux-2008-03-xfce-i386.iso 391MB) 2.6.26 kernel, maybe more more compatible with Debian Lenny.