If you don't wish to make the jump to vertex arrays and a VBO just yet, there are some simple changes you can make to get more efficiency from even immediate mode.
Yes, immediate mode is still the slowest option, but it's not THAT slow - Quake used immediate mode back in 1996 and despite that it will get you well over 25 fps on modern hardware. So bear that in mind when considering the rest of what I have to say. Moving to vertex arrays or VBOs will (eventually) get you more speed, but unless you tackle the root cause of your performance degradation (which is actually the fact that you're doing a separate transform per-sprite) it's not going to be much more speed (it may even be slower).
So let's look at your sprite transformation. This is actually quite a simple transformation matrix that is built on the CPU (even in OpenGL with hardware T&L - it's only the final transform of position by MVP matrix that runs on the GPU) so we can take advantage of that knowledge and make immediate mode go faster.
Before I go into much more detail about how to deal with that, the first thing you need to know is that you have a classic case of an immediate mode anti-pattern at work here. It manifests as this (C/C++ code but it should be obvious what the Java equivalent is):
for (int i = 0; i < NUM_SPRITES; i++)
{
glBegin (GL_QUADS);
// glVertex/etc calls here
glEnd ();
}
The simple solution to this is:
glBegin (GL_QUADS);
for (int i = 0; i < NUM_SPRITES; i++)
{
// glVertex/etc calls here
}
glEnd ();
If you don't believe me then build it, run it, benchmark it. Ramp up the value of NUM_SPRITES to see how each approach performs as the count increases. Each glBegin/glEnd pair counts as a "batch" in immediate mode, and by putting them outside the loop you get better throughput.
So how can we use this to acelerate your case? Quite easy. Instead of using the matrix stack to do transforms, let's build the matrix and apply it to each sprite in software ourselves. This seems a mite counter-intuitive, but stick with me - it's still going to be faster than breaking batches by having to do a separate transform per-sprite.
Our loop now looks like this:
glBegin (GL_QUADS);
for (int i = 0; i < NUM_SPRITES; i++)
{
// evaluate transformation matrix for this sprite
// apply transformation matrix to sprite positions
// glVertex/etc calls here
}
glEnd ();
So how do we do those two new steps? Just by using the OpenGL documentation to build the matrix; e.g. the matrix for glRotate is given here: http://www.opengl.org/sdk/docs/man/xhtml/glRotate.xml and for glTranslate here: http://www.opengl.org/sdk/docs/man/xhtml/glTranslate.xml. Another, better option is to grab a matrix library; I'm not familiar with Java so I can't speak as to availability of such but a quick Google search should turn up results.
It's also worth noting that you have a potential shortcut here too - if for a given sprite the rotation angle is 0, then instead of doing a full matrix transform you can just do:
glVertex2f (x + half_size, y + half_size); // and etc...
Once you have that part resolved, THEN is the time to consider porting to vertex arrays or VBOs, not before. Because, like I said, your real bottleneck here is not use of immediate mode, it's doing a separate transform per sprite. Porting the code before addressing that will still leave you in a position where you have to break batches at every sprite, and any performance gains will be quite marginal (a bad VBO implementation may even run much slower).
IMO people are often too trigger-happy about recommending VBOs as a solution as soon as they see any immediate mode code, and can sometimes fail to analyze the code properly and identify that the real bottleneck may be elsewhere. Of course a VBO will be the optimal solution longer-term, but address that real bottleneck first.