Go ahead and install Linux to that new free space. If you are paranoid, when the Linux install proceedure goes to boot, you can boot into Windows 95™ and make sure it still runs OK.
When it comes to partitioning the disk, if you are like most people, you'll make a 600M Linux partition (which is pretty comfortable) as well as 80M of SWAP (which is more than enough).
At this point, you should be able to install whatever distribution of Linux you have without any trouble.