Since it is not reading the floppy correctly, this tells me one of two things is most likely wrong:
1. BIOS set to boot from C:\ first, which you have deleted (it is a non-system disk now).
2. Floppy is not a proper boot disk.
To solve problem number 1, go into the BIOS setup and make sure that A drive is first in your boot list (unless you have the option to install from CD-ROM, which is unlikely if this is an older machine.
To solve problem number 2, you need a proper boot disk. The easiest spot to find boot disk images is http://www.bootdisk.com. You can find a boot disk for a variety of OSs.
If you want to make sure the hard drive is completely "fragged", you will most likely want a DOS disk with fdisk on it (as you stated you have already done). Delete everything and start fresh again.
Depending on the OS, you will want to start with the proper boot disk. The important thing here is FAT16 versus FAT32 versus NTFS (or even Linux partitions). Most boot disks willdo the partition setup for at least one of the partitions for you, or will provide tools like format and fdisk to aid you in this.
My suggested steps:
1. Create a boot disk (from www.bootdisk.com) for the OS you are going to install.
2. Make sure the drive is completely cleaned.
3. Run BIOS setup and make sure you have it checking drive A first
4. Start the computer with the boot disk.
5. Install OS.
Gregory A. Beamer
MCP: +I, SE, SD, DBA