CC,
I had the opportunity of upgrading a range of Compaq PCs with 10 GB disks in the PIII 450-600 MHz range, so probably of the same vintage as yours.
I found that 60 GB was the largest drive that could be accomodated by the systems.
While not saying that you can't fit a drive larger than these (especially if you can update the BIOS to a recent version), I would be cautious about > 60, though 80 might not be a problem.
I left the original 10 GB disk in as the system disk and added a 40 or 60 GB disk as the Data disk - obviously you need to have space, power, connections sufficient to do this.
An alternative would be to add a SCSI card and then you are no longer limited by the IDE restrictions.
As regards the type of drive, you can use any drive that supports an IDE interface. The speed of the interface will be limited by what your PC supports, not what the drive is capable of. That said, the faster the drive spins the lower the seek time, so you may as well go for a drive with a high rpm.
There's some useful info on interfaces
here
HTH
SD