G4/G3 comparison:
According to benchmark tests performed on Mac hardware the G3/G4's integer performances (does not utilize Altivec) is basically the same at similar clock speeds.
However the floating point performance is roughly 30% better at the same clock speeds for the G4. (And of course there are often huge additional performance gains for Altivec optimised software.)
Some official data from Motorola and IBM for some rough comparison:
------CPU----------------------------Spec95 (int)-Spec95 (fp)
-------------------------------------------------------------------------
G3 750FX @ 900 MHz--------------39.9 ---------21.1-------
G4 7451 @ 733 MHz----------------32.1 ---------23.9-------
The integer performance difference is about what you would expect, based on the higher G3 clock rate. Yet still the G4 is about 12% faster with regard to floating point performance.
My conclusion, even when taking out of account the very cool Velocity Engine, the G4 is a slightly better overall performing CPU than a G3 at the same clock rate.
Regarding the Velocity Engine (the G3 has none), AltiVec adds 128-bit-wide vector execution units to the PowerPC architecture.
Here you can find a well done introduction. The amount of performance gains differ greatly between different types of applications and how well they are optimised to use Altivec's benefits. Recent MacOS versions of Adobe Photoshop are well known for being well optimised for this Velocity Egine, and
here you can find some interesting (non-Apple Computer, Inc) benchmark comparisons.