On my old iBook (G3/ 10.1.5/ 500MHz), I found that the visual effects very slow after upgrading to iTunes 4. Unselecting the option "Use OpenGL" brought back the speeds I was accustomed to.
[robg adds: I've heard this before, but I'm not sure why it would work like this...]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20031012081258706