I recently put a new HD into my 14" iBook G4 (it had a 60GB 4,200rpm drive in it). It was probably the most scary time of my life! I wouldn't recommend doing this unless you have a spare afternoon, a lot of patience and very nimble fingers.
If you are going to do it, use a Seagate or Hitachi 2.5" PATA/IDE drive. after checking out alot of forums and HD testing sites, i chose the Seagate ST910021A, which is a 7,200rpm 100GB drive, you might want to use a 5,400rpm drive though as they are quieter and can have larger capacity.
Definitely use the ifixit guide and screw guide printout, there are a lot of screws to come out of there! i found it impossible to find a spudger in any stores in the UK, but used a plastic tie hook, which did the trick and left no marks on the case.
The worst part is trying to prise the trackpad and speaker power connectors from the logic board through little openings in the heatshield, without tearing the connectors of the board.
Having said all this, i'm glad that i did it and if you're careful it's definitely do-able. But then i don't have applecare!! Good luck if you decide to do it. 🙂