Realmente no te recomiendo lo de partir el hdd a la mitad. Lo que te recomiendo es lo siguiente:

• Dos particiones iguales y pequeñas para los SO (Por pequeño entiéndase unos 25~30 Gb. Para Linux serán suficientes, pero para windows dependerá de tus necesidades)
• El resto del hdd como una partición para archivos, compartida por ambos SO (así tendrás todos tus archivos en un solo lugar, y si necesitas formatear algún SO, estarán a salvo)

La manera de proceder, si gustas seguir mi consejo, es la siguiente (antes de empezar, desfragmenta tu hdd):

• Baja algún editor de particiones para windows (particion manager, partition magic, etc)
• Redimensionas la partición actual, hasta el tamaño que hayas elegido (Lo suficiente para que tu instalación actual quede con algo de espacio disponible, por si las dudas XD)
• Te quedará un gran trozo de hdd como "unallocated", selécciónalo, y crea una nueva partición, que será la partición para Linux (igual recomiendo unos 30 Gb. El formato de la partición da igual, de momento todas créalas en NTFS)
• Ahora tendrás dos particiones, y aún mucho espacio sin asignar (unallocated). Selecciona de nuevo este último, y crea otra partición. Si tienes 1 Gb o menos de RAM, créala del mismo tamaño que ésta. Si cuentas con más de 1 Gb, créala de la MITAD de tu ram.
• Ahora tienes 3 particiones, y aún mucho espacio sin asignar. Selecciónalo de nuevo, y crea una última partición, del máximo tamaño que te permita (es decir, de todo el espacio que te sobre).
• Listo, dale al botón de aplicar cambios (hasta ahora tu hdd no ha sido modificado en absoluto). Tu pc se reiniciará, y aplicará todas las modificaciones solicitadas en el programa. Una vez que termine (paciencia, que tomará un buen rato), iniciará normalmente con windows xp, y desde mi pc podrás ver todas las particiones que creaste :)
• En este punto, ya estás listo para instalar la distro de Linux que desees. Recomiendo Ubuntu, o Linux Mint (yo uso Linux Mint 9), por el gran soporte que tienen ambas distros (si se te presenta un problema, una gogleada y seguro lo resuelves). El procedimiento para instalarlas es muy parecido, está descrito aquí (usando un pendrive usb)

Cualquier duda pregunta con toda confianza, que esto no es muy sencillo, y puedes quedarte sin SO's en tu pc :S