Welcome to Apple Discussions.
I suspect you won't find much Linux experience in the iMac forums - although if you post elsewhere in Discussions you'll find hard-core users who live in Terminal; but I suspect you issue here may be that your replacement Optical Drive is not bootable.
Try booting from the original install/restore CD that came with the iMac (insert the CD and hold 'C' straight after the start-up chime).
To find out more about your computer/ OS X version go to the Apple Menu > About This Mac > More Info.
Once you've found out what the model number of the optical drive is go on to the xlr8yourmac's drive database and read if and how other users have got that drive booting their Macs.
Never heard of an Apple Firmware CD - but there is a firmware update that can be installed on the iMac G3 - but you must be booted in to OS 9 to run it and not OS X.
I had some small issues when starting on my G3 with OS 8.something. Then I had a stroke of genius (well sorta). Clicked on the little apple, go to control panels and then startup disk. Choose your Ubuntu disc (or CD Rom Drive if you don't have the disc in) and then reboot. Cured my issues. Hope this helps, please let me know.