I couldn’t figure out how to do this for the longest time and finally found the answer, thanks to disco_bob on the Apple Support Communities.
When in the visualizer, press the Control key + Command (⌘) + F.
|iTunes 11 visualizer playing Mannheim Steamroller in windowed mode|
Finally, no longer stuck in full screen mode!
For more hidden iTunes visualizer controls, see https://support.apple.com/kb/PH19483