I can't think off hand where you'd find an accurate list of "installed size" of various distros.
If I understand you, you have 4Gib of space on your disk or flash-media, onto which you can install a distro, right?
Ubuntu would certainly be one of the largest distros installed, and if you have 4Gib to play with, I'd venture a guess that it would be pretty much filled to capacity, if not full.
Most distros can be installed in a selective fashion, that is, you can pick and choose what you do or do not wish to install. Omitting such things as heavy bloated desktop environments like KDE and GNOME, or omitting something huge like GIMP, just as examples, can trim down the installed size of many distros.
On average, a full-meal-deal install of Ubuntu, Slackware, or maybe Sabayon, or another very full distro with lots of software, will consume over 3Gib of space, but not as much as 5 Gib.
As a further example (example only), a Slackware installation can be trimmed down A LOT smaller than this, maybe down to between 1 and 2 Gib while still having a lot of stuff installed. I do not believe Ubuntu offers this sort of flexibility when installing; rather, it's a all-or-nothing affair.
Puppy is VERY small; I believe the installation is only a few hundred MB, as the installation CD is only 50MB in size, and considering this small-ness, Puppy is a really nice little distro, with lots of drivers and networking configurators included.
I'm not familiar with "Ubuntu Netbook Remix", but if that is not already what you have, you might look at that too. I have no idea what size that is, but I'd guess it's smaller than ubuntu as it is tailored for netbooks.
Also, Xubuntu is likely a fair bit smaller than Ubuntu, but I can't say by how much..
Other users of other distros will have to drop in and provide estimates of installed size for other distros besides what I've mentioned here, because it has been quite a long time since I did a full install of *anything* besides Slackware.