Cloudz, when I loaded redhat I followed recommendations for the boot loader on a separate partition. ie: I seem to recall it was like 500 mb or so. If you tell me which linux you want to load, I can look up the partition recommendations and see if all the partitioning, format and boot loader tools are available on the disc you want to use.

Are you going to download the iso and burn it, or are you buying a disc?

Just let me know which one you want to load and I'll try to help you. With 40 gigs you have plenty of room to set it up right the first time and avoid headaches.