Only the G4 Sawtooths released prior to the OS 9 release will boot 8.6 - OS 9 came out in January 2000 if memory serves -September 1999 to January 2000 should boot OS 8.6. However, there's another caveat - not all of the G4 400's released between the beginning of September and the middle of October are Sawtooths (with AGP graphics etc.), so if you do go looking for one of them, be aware that there are a number of differences - you may find yourself looking for a rather small subset of machines!
Have a look at
http://www.everymac.com for all the details.
With the 500 MHz Sawtooth, you'd be looking for an even tinier subset - they discontinued them after mid-October 99, so the ones that boot 8.6 were only distributed for 2 months. They reintroduced them in February 2000, but by then, they came with OS 9.
As for running X, my 400 MHz Sawtooth does a reasonable job, though I'm about to do the upgrade to Jaguar (still on 10.1.5)/new harddrive install this afternoon and will be very interested to see how that affects speed. Right now, I find that I do everything but Photoshop & email on my Powerbook - once you get a taste of speed (and particularly browser speed with Chimera and Safari!) you REALLY notice the difference. I am considering a processor upgrade for the Sawtooth though, since purchasing a new machine would be at least 4X the cost to get what I want and I think I can get at least another year or maybe more out of the it this way. The processor upgrades don't work with 8.6 though, so that isn't an option for you.
Another route to consider would be upgrading the G3, as Krissel suggested. I've got a Sonnet 500MHz G3 upgrade in our G3, but so far haven't tried installing Jag on it. Right now it has 8.6 and 9.2.1, so I'm curious to see how it does with X. It isn't really high on the "to-do" list though - I'll let you know how things go if I get to it!
You should probably have a look at
http://www.xlr8yourmac.com and see how what people have said about the upgrades and X. Seems most have been happy with them. One caveat I hadn't thought about - Jaguar doesn't recognize serial ports, so if you're using any older peripherals this could be an issue.
