You can just resize the Windows partition and leave free space for Linux installer. It can create partitions for you and format them.
You need a / (root) filesystem and swap (and may have more partitions, for example /home for your private files). They can all be extended. Swap can be ~500MB (or even less, 300-400MB), the rest for main partition.
The MBR (I guess you mean the boot menu) will not be updated the right way during installation. You need to do this yourself. During Linux installation choose not to install LILO in the MBR. Install it in one of the Linux partitions. Create a boot disk when asked.
When the installation's completed, boot from the floppy, log in as root and make an image of LILO:
dd if=dev/hda? of=boot.lnx bs=512
Where /dev/hda? is the right partition name (the one you installed LILO to). Copy the file to Windows partition (via floppy). When in Windows, open boot.ini and add (at the end):