But your question is about formating because it is not that the 6100 has a HD size ceiling, but that either the drive you are using, or the software you are trying to format it with is not supported and that is the issue. Formating the HD in another machine with native IDE support, and then transferring the drive back into the 6100 might take care of your issue.
For the 6360 you need to hold the "C" key down to boot from the CD. You can also try "Command+Option+Shift+Delete" to shut off the internal HD and it will look to the CDROM for a bootable volume. If that is not working than either your CDROM has an issue, or your copy of 8.5 is defective.