I blame poor integration with X in Java.  but that's just a guess.  here's the situation:

I spent last year teaching Processing, using Linux on some pretty machines (2Ghz athlon dual-cores), and just consistently felt that it was extremely slow.  Any size larger than about 400 or 500 pixels gives a big hit to the framerate; even PDE feels slow, typing has small but irritating lag, etc.   Doing the same things on comparable, or less-powerful, macs, didn't have these issues.  Weird and annoying, but I didn't want to post something like "Processing is slow! Argh!" without some numbers to back it up.  So I tried to come up with some benchmarks and run them on identical hardware under at least Windows and Linux to try and gain some insight into what's going on.

Here's my little benchmark app:  1000 lines per frame, from black to white, printing out timing data after every 256 frames.

/////////////////////////////////////////////////////
float c;
int starttime,endtime;
void setup()
{
c=0;
size(1000,700);
starttime=millis();
frameRate(60);
}
void draw()
{
background(127,127,127);
stroke(c,c,c);
for(float i=0;i<1000;i++)
{
line(random(1000),random(700),random(1000),random(700));
}
c++;
if (c>255)
{
c=0;
endtime=millis();
float dt=endtime-starttime;
println("Total time=" + dt + " ms    Average Frametime=" + (dt/256));
starttime=millis();
}
}
//////////////////////////////////////////

Test machine is an HP Pavilion ze2000 laptop, nothing too special but not ancient and creaky either.  

AMD Sempron 1.6 GHz
ATI Radeon Xpress 200

here's the numbers (average frame time in milliseconds.  smaller is better).  the target framerate is 60fps, or 16 ms per frame.

=== WINDOWS XP HOME : NO OPENGL ===

:: 1000 lines
1000x700: 91 ms
400x400: 22 ms
100x70: 16 ms

:: 100 lines
1000x700: 36 ms
400x400: 16 ms
100x70: 16 ms

=== WINDOWS XP HOME : OPENGL ===

:: 10,000 lines
1000x700: 255ms

:: 1,000 lines
1000x700: 16 ms

=== UBUNTU 7.04 : NO OPENGL ===

:: 1000 lines

1000x700: 263.5ms
400x400: 60ms
100x70: 16.1ms

:: 100 lines

1000x700: 121 ms

:: 10 lines

1000x700: 121 ms

:: 0 lines

1000x700: 120 ms

=== UBUNTU 7.04 : OPENGL ===

:: 10,000 lines

1000x700: 184.39 ms

:: 1,000 lines

1000x700: 16.1 ms


Conclusions:

In Linux, without OpenGL acceleration, you can't have a large window size, period.  It appears that just the overhead of the draw() loop and background() call take up 120 ms, or around 8 fps, at 1000x700.

OpenGL acceleration solves the problem, giving full 60fps at 1000x700 for the 1000 lines test case.

Windows fares a little better without opengl, getting a frame rate of close to 12fps at 1000 lines, 1000x700, and getting around 28fps at 100 lines at 1000x700.  While the stage size is still a big factor, it's more sensitive to the number of lines.  

With OPENGL, again we get full 60fps at 1000 lines, 1000x700.  Interestingly, when we push the line count to 10,000, the linux ATI drivers apparently beat the Windows ATI drivers with 184 ms/frame vs 255 ms/frame.  

I don't care about windows at all, actually, I'm just interested in making Processing run faster in Linux

so, questions:

should I just ignore this and always use OpenGL?

is the reason mac 'feels' faster because the awt/java2d/whatever is secretly using hw acceleration?

is there any difference in performance between different versions of java?

I'd like to chime in on the Mac speed bump you're bringing up.  When I run your benchmark in regular mode @ 60fps, my results are as follows:

Total time=22729.0 ms    Average Frametime=88.78516
With around 100 percent CPU usage (100 on one core)

OpenGL:
Total time=4096.0 ms    Average Frametime=16.0
Total CPU usage at around 30 percent on one core

Average frametime seems to top out around 240FPS at 4ms.
Total time=1311.0 ms    Average Frametime=5.1210938

Therefore, I don't see much of a speed improvement on my mac at least w/ the default rendering.  I'd like to know more about your Linux speed issue, as I'm looking into purchasing a few Linux boxes for processing.

(This is on a 2.4ghz Macbook pro with a 8600gts mobile.)