Using a reasonably recent version of LILO (21.3 & above) (Mdk 9 should be all right), you can set up your Linux distro wherever you see fit. You can boot past the cylinder limitation with no problem (using the lba32 parameter in lilo.conf).
As for dual-boot, I highly recommend XOSL v1.4 (http://www.xosl.org
I would also strongly suggest to clearly separate Windows from your data.
For example :
Primary 1 - 6 GB NTFS for Windows XP.
Primary 2 - 6 GB for Linux ("/")
Extended - the rest of your drive
--> logical 1 : XOSL dedicated partition (smallest you can set ~8MB)
--> logical 2 : Linux SWAP (512 MB should be okay)
--> ... (a data partition for Windows, a data partition for Linux you could use for /home for example... Your choice : you're not limited by the number of logical drives, while you can only setup four primary partitions, or three primaries + one extended).
Then install LILO to the superblock of the root partition (NOT the MBR !!), install XOSL to its dedicated partition, and set up the boot menu accordingly.
Good luck !