I ran woody on a 170MB hdd not so long ago, and had room to spare. Which I promptly filled with useless servers like apache, samba, a mailserver, etc.
A Debian base install which is fully functional (can get on the internet and stuff, even with ppp) can be done in 50MB easily. The ISO you install it from is 30MB only. Of course you can't install kde and other desktop stuff on it, but xclient libs and a few chosen X program will fit.
For your networkproblems, just get a recent 2.6.x kernel and chose the forcedeth driver when compiling.
For dualbooting: you need to install the Linux bootloader in the MBR (lilo or grub). Then edit its config file to add a Windows entry for booting. I prefer grub: it looks better in the default bootmenu and has neat features like the changing of the settings while booting or the chainloader.