I installed Debian on a Power Mac 8600 a year or so back, and it was one of the most aggravating things I have ever done.
To first answer the CD question, as far as I know it is impossible to get an old world Mac (anything before the bright-colored G3 line) to boot to a CD other than those with Apple's proprietary boot loader. So floppies are your only choice.
I am not sure why your boot floppy would not work. Mine did, but I recall having to search around for a bit before I found the proper ones. You could also just have a bad download.
Looking past actually getting the thing to boot to the floppy, you will then have the issue of getting Linux installed and bootable. While it is possible to directly boot to Linux on an old world Mac, it is much much easier to first install Mac OS, and then use a program called BootX to actually launch the kernel and initrd.
If you don't have an old Mac OS install laying around (I definitely didn't), you can download a Mac OS ~7 boot floppy from the Internet and use that. I was able to format the HDD and copy the contents of the floppy to it. The machine would complain about this not being a proper installation of Mac OS, but it worked well enough for my purposes.
I was not very happy with using BootX, but considering the amount of configuration required for getting Linux booted without it, it just wasn't worth my time (especially since this was just a bit of tinkering in the first place, and didn't really have a point).
If you do use BootX, you will need to figure out how to get the kernel and initrd onto the Mac OS partition as well. The version of Mac OS I was using didn't support USB, and certainly couldn't read the Linux partition, so I was forced to write the files to a ZIP disc with TransMac on my Windows machine.
This page has pretty good information on what you would need to do to get Linux on an old world machine.
I will try and find the boot floppy I used, and see if I can't figure out were I downloaded it from or at least get an MD5 off of it.