Go for the PowerBook G4 and never look back.

Obviously it has got the fastest G4 CPU, your model has got minimum 64 MiB VRAM, flawless out-of-the-box suppport in MorphOS, great support in Linux after some tweaking. If it's a PB 5,8 you even get full support in current Linux without tweaking (only installation of WLAN + audio-drivers needed).

Also spare parts are available at reasonable prices and you'll find good repair guides on the net (which holds true for almost all PPC-Macs).