The hard drive just failed (epically, if that's a word) on my Early 2006 Core Duo iMac. I took the iMac to my local Apple Store, to have my diagnosis confirmed and to rule out other problems. The Genius for helped me was very good, and the free testing showed a failed hard drive and no other problems. He then checked and informed me that it would cost $284 dollars for a replacement 250 GB hard drive (not in stock, either), and that the work would cost an additional $85. When I mentioned that I could get a new 500 GB drive for about $50 and that I was tempted to do the job myself, he suggested that was a good idea. He then spent some time recommending where I might purchase a drive, and gave me some tips for opening and working inside my model iMac.
Anyway, I ordered a Seagate 500 GB drive for $40 at newegg.com, and spent several hours opening the iMac, moving the lcd and then removing the (fried) hard drive. Cleaned out a lot of dust and put in a new 3V battery too. Once my new drive arrives I'll reverse my steps and pray that everything works. 🙂
Unless you like working inside computers, I'd follow the earlier advice and have an Apple Store install a drive that you have already purchased.