I've got a notebook I installed Linux on, beside Windows 95 that was pre--installed. I squeezed the Windows partition to 500 Mb, making space for a 240 Mb Linux one. Small though the latter may seem, I've managed to install a fairly complete Linux system on it, based on Red Hat 4.1 and some magic to save as much space as possible.
If you're in need for space, the indications you'll find in the following sections will free up a considerable chunk of hard disk. The only caveat I'm giving you is: don't blame me if something goes wrong! We'll be using a couple of programs that worked fine for me, but are inherently dangerous. You've been warned.