Hi there,
for the G4 you have the following options:
ATI Radeon 9600 256MB, ATI Radoin 9700 128MB, ATI Radeon 9800 256MB, and Geforce 4Ti 128 MB. These are the traditional choices you have. If you want to connect two 23' displayse at once or one 30' Apple display, you can only use the ATI Radon 9600 or the build to order Geforce 4Ti.
If you don't need the dual screen option or want to hook up to apples mega 30' screen, then your best bet is indeed the Radoen 9800 mentioned above.
This version is available also in a 128MB version by the way.
Two more things you want to know: The Radeon 9800 is a really "hot baby". If you go for this card you will most likely increase your internal temperature. If you operate already on the ege temperauture wise I would still got with the 9600.
The point you mentiond regarding Leopard, these cards will support Leoplard on the velocity engine.
All right, these cards mentioned above are build to order cards or original cards. There are ebay shops you can get them. In case you are more "experimental" you can go also with flashed pc cards. There are even better choices available, however they are not "Apple original".
These cards are Radeon 800 XT and Geforce 7800 GS as long as I know.
Happy choice!