I would recommend looking at Ambrosia Software for some games such as Escape Velocity, Override, and Nova. All work just fine with your G3. They are open plug-in games, meaning anyone can change the entire story-line.
Myst works and possibly Myst 2 Riven (I am not to sure about Myst 2 as it crashes on my iMac, see sig. for specs).
The fps, Unreal Tournament Game of the Year edition, Links 2000, Ghost Recon., Tomb Raider to name a few. They all run fine on my G3/300, OS 9.2.2,
320MB RAM. Still play UT online, cable connection and quite respectable in terms of game play.
I would get Age of Empires II. I haven't wasted more hours on any other game then AoE II. It ran great on the old 333 MHz iMacs. I was also able to run it on my 500 MHz G3 a while back. But yeah, AoE II should run well.