10.04 versions:
http://cdimage.ubuntu.com/ports/releases/10.04/release/
(the long term release version)
or
http://cdimage.ubuntu.com/xubuntu/ports/releases/lucid/release/
(also LTS +uses the less demanding XFCE desktop)
Xbuntu might be better, strongly recommend it since it is less demanding on the system. Esp. if you mac shares it's system memory with the graphics card. I am not sure but my guess is it does. I can use 800MB of RAM on my Ubuntu system without even trying. (web browser, email, skype).
choose the correct CD image for your machine and it should work.
Due to the age of the computer you may have some problems with the graphics driver or maybe sound. Being familiar with the command line would be a bonus if you need to fix something without a graphical environment. The ubuntu forums are your friend, everyone finds solutions to problems there.
The linux part I can offer some info, I work with newer macs and have yet to have an install problem, i never dealt with the model you have.
I am not sure your mac supports booting from USB, prob. only firewire, I am not sure thou.
Someone here that knows more about macs might be able to offer an idea of using another computer to install mac os over a network (Ethernet connection).
OR
best option would be cloning/imaging your original hard drive and applying that image to the new hard drive. Free one called drive image XML should work I have used it before.I have also used others. Your old hard drive is in good health so start with the Drive Image xml and if it doesn't work try another.
here is a list of drive imaging tools:
http://mysoftchoice.com/c/backup_tool/clonezilla_vs_DriveImage_XML_vs_g4u_vs_macrium_reflect_free_vs_paragon_drive_backup_free_vs_partimage
Seems like it would be your easiest and best option for your mac OS install with the equipment you have listed.
(and don't make it hard, I have left my own laptops with hard drives partially installed in a safe manor while imaging, all you need is an external hard drive or in some cases an available network share)