As long as you have enough memory (128MB or more should do well), the hard disk won't make a whole lot of difference. Just get a cheap one; 10GB at 5400RPM with ATA/66 would probably be plenty.
Concerning a Linux distro to get you started, I'd suggest either the latest version of Redhat or Mandrake. Use one of those until you get comfortable with the command line (it will take a while, so don't get discouraged and give up), and by then you'll be wanting to move to something like Debian or Gentoo.