1) This is a very hard question to answer. Each distro has it's own personality. Try one and if you don't like it try another. If you do a search on this board you will find quite a few opinions. I would suggest either Red Hat 6.2 or Debian on the Linux side. I also like FreeBSD, OpenBSD and BeOS. Solaris is always good to know too.
2) If you are installing 2 OS's you should be able to just partition and install.
3) Win2k SHOULD notice that another version of windows is on the drive and put it in the bootloader. Doesn't always happen though.
4) You can fit many OS's on a drive. It is just a matter of partitioning, patience and a good boot loader.