So my application was looking uggggly... I tried setting and checking the color format for (what I thought was) everything, from the window to the loaded images and it did not help. So then because of this line in the wiki, I thought it was only natural:
Accuracy of colors is more limited on Android. Most screens will not be full 24-bit color, which especially shows up with gradients, highly detailed color sketches, or when using a lot of transparency. With gradients, you might see banding of colors, or when using transparency, you might see halos or visual artifacts left behind. These are just mathematical artifacts due to how colors are handled, subject to limitations of the screen.
Then I tried OPENGL and saw the colors where rendering correctly (24-bit). 
So I took a look at the processing source, and figured out it has to do with the (non-GL) surfaceView used for the sketch.
So I took a look at the processing source, and figured out it has to do with the (non-GL) surfaceView used for the sketch.
Solution: Include this in setup():
- getSurfaceHolder().setFormat(1);
Edit: Put it in onCreate() after calling super.onCreate() if you don't want your screen to freeze after orientation change!
It's easy to not notice this issue, but it is there! It's most visible in darker colors where you can see a lot of banding.
Edit: Here is a screenshot (brightness increased for exaggeration):
So why is this not the default format? Is it a bug or was it done like this on purpose?
p.s. I'm using 2.0b8 and a Sony-Ericsson Xperia Arc S.