Apologies, "Yikes" is the codename for the Power Macintosh G4 (PCI Graphics) -- it's the same platform as the blue-and-white Power Mac G3, but with fixed IDE and no ADB port.
Barefeats was a mac performance web site in the G3/G4 era and has some Quake 3 data: https://barefeats.com/quakeX.htm
Warcraft 3's requirements are for a G3/400 with any 16-meg ATi or nVidia graphics card.
My recommendation if you want those newer games to work better is go directly t a machine that started its life as a PowerMac G4.
Upgrading older machines, and G4-upgrading a G3, will get you a speed boost, but it likely won't be as fast as a machine that started at whatever speed you choose.
AGP graphics G4s pretty much start at 400 or 450 and for these games basically any of them should work great. The first few generations have 100MHz buses (same as the blue G3 and the PCI graphics G4) but faster G4 upgrade CPUs exist for them and the AGP graphics are faster.
The middle group have 133MHz buses and that's probably the sweet spot.
The last group (the three "mirrored drive door" generations) are probably not worth it if 9 is your primary aim, but would make great OS X machines.
The games at the tail end of the range you mentioned do run on OS X too, so you can basically run them on any G3/4/5 as well, I don't see why they won't run on newer versions of OS X than what the specs mention. Depending, it may be worth thinking about splitting this range into two -- one your 6360 can run and one a hypothetical PowerMac G4 can run.
To your question about G4 upgrades: In general no, if you put a G4 upgrade in, all the old software will still run if you had some reason to want, say, 8.1 and a G4, that would work in a Beige G3. G4s also work with system 7 in the PCI PowerMacs.
When this stuff was all new, most of the reason people did upgrades was to get some existing pro app to run better. There were times when faster-than-stock upgrades existed while the machine they upgrade were still on sale, but the other half of the use case is speeding up used machines. There was a moment when a PowerMac, some RAM, a new disk, and a G4 upgrade cost a bit less than, say, a new intel iMac and PPC still had full software compatibility (10.4/5 had very long lifecycles by today's standards).
w/re 8.6: G3s are better if you want 8.6 specifically (although the yikes and sawtooth (first-gen agp graphics powermac g4) will run it) but some of your games require 9 specifically and on any G3 or better 8.6 and 9 will be functionally the same speed. There's a handful of apps that run better under 8.6 than 9 but none of them are games or things people are want to tourism in our modern times, it's nearly exclusively stuff for Specific Industries.