+1 on Eyeyougren for the USB 2.0 and FW400 cards. Also CPU upgrades are very worthwhile, but can be cantankerous depending on the brand(buy Sonnet if you can) and can also cost a bundle. You will need a ZIF socketed upgrade for the G3, and depending on the brand you may or may not have to tinker with jumpers on the logic board to get it to run at the rated speed. Additionally, Apple "locked out" the firmware on these from actually recognizing G4 processors, so if you buy an upgrade be sure you get the install CD with it-this should "unlock" the firmware.
Your G4 looks to either be a Yikes!(PCI graphics) or Sawtooth(AGP graphics) model. A Yike! uses the same ZIF CPUs as the G3, and many upgrades that will work in a B&W G3 will also work in a Yikes!. The Sawtooth uses a totally different CPU socket, so you will need to look for Sawtooth CPU upgrades.
Unfortunately, you're a bit limited in terms of GPU upgrades for either of these.
For PCI graphics models(both the G3 and the Yikes! G4), the best "official" Apple CPU upgrade is a Radeon 9200. This is a great card, but does not support Core Image. Core Image improves the performance of Tiger, and especially Leopard, although getting Leopard on one of these systems is not overly easy(and the G3 will need, at a minimum, a G4 upgrade). The nVidia FX 5200 is available in PCI versions and supports core image, although you will need to buy a PC version and flash it as there is no official Mac PCI 5200.
If you have a Sawtooth G4, the GPU upgrade paths are a bit more numerous although the 2x slot locks out many of the cards that Eric and I have been experiment with in later G4s. The GEForce 4Ti is the best "official" option for this computer, but is hard to find and often expensive. The stock card is a probably a Rage 128, and(in increasing order of performance) a Geforce 2MX, Radeon 7500, Geforce 4MX, and Radeon 9000 are all pretty readily available in Mac editions and will give you some increase in performance. It's probably debatable whether the 4MX or 9000 is better-they are actually pretty close, and I'd base the decision on whether you prefer having a VGA or DVI port.
To my knowledge, there is one Core Image card available that will work in 2x slots-the nVidia 6200. Unfortunately, this was not made in an official Mac edition, so will need to be flashed. I don't think you need to tape pins for it to work in a Sawtooth, although I could be wrong on this and taping it certainly won't hurt anything.
Much of above is also true of your Cube, although you also are limited by space constraints. The only cards that will "drop in" to the Cube are the 2MX, GeForce 3(rare-I've been looking for one for about 2 months) and Radeon 7500. The 2MX can use the same faceplate as the stock Rage 128, so is the easiest upgrade for a cube. It runs HOT in a cube, though, and you need to at least consider a base fan if not a fan directly on the card. A flashed 6200 will also work in the Cube with the pins taped.