I've seen many complaints that iTunes visuals defaults to the same visual each time it's started. Clicking the visuals button with the option key pressed will randomize the first visual. Also, for those of you with more than one mouse button, I've found that clicking the middle scroll-wheel button changes the visual while playing.
[Editor's note: A middle-button-click doesn't do anything on my MS Intellimouse in iTunes...]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20021009061718669