I know this thread is a month old, but I have invested serious thought and work into the project, and I'd like to post an update to show that I aprecciate your answers, and to help other people with similar issues.
Do you have any profiling tools that allow you to measure CPU and GPU timings independently? The first step will be determining which processor is the bottleneck, so you can focus your optimisations usefully.
I believe that you have a very good point here; I have mostly been "optimizing blindly", which is considered bad practice. I have tried / considered the following options:
1. Android SDK Tools: the profiler shipped with the SDK shows CPU time, but not GPU time. Also, it profiles my own application, but I would like to see what's going on in the whole system. Google has recognized this and published a tool for system-wide profiling called systrace, but it's only available for Jelly Bean. The same goes for dumpsys gfxinfo which in combination with the Jelly Bean developer option "Profile GPU Rendering" outputs a stat about how much time is spent processing, drawing and swapping UI. See Chet Haase and Guy Romain's excellent presentation about Android UI performance for more information about those tools. For me, they are not an option, I am stuck with Honeycomb for various reasons.
2. Log output: yes I know it is stone age, but I thought it would be interesting to see how much time my application spends in my move() (CPU) and draw() (GPU) methods. The results are not very conclusive; I guess this has to to with multithreading and the way Android handles vsync.
3. NVIDIA Tools: there is a tool for Tegra 2 platforms called PerfHUD ES that looks very promising: detailed information about draw calls and lots of other GPU-related information. I am currently trying to get this running on honeycomb. Any help aprecciated.
Option 1: Software transform the vertices. That is, do the matrix multiply on the CPU, then you can send all the cubes in one go.
Option 2: 'Hardware skinning' style solution. Instead of doing one cube at a time, put 16* cubes into your VBO. The vertices for each cube have indices, which you use in your vertex shader to look up into an array of matrix uniforms.
Both of your options seem very reasonable approaches to take. I decided to implement option 2 first. The OpenGL ES specification calls this method "Dynamic Indexing". It took me an hour to rearrange my application accordingly, and a whole day to find out how to get hold of the vertex index inside the shader and use it to address my transformation matrices. It's not straightforward on OpenGL ES 2.0 because for some fucking reason they decided to leave out the crucial gl_VertexID variable there. Sorry, but this tiny little detail really drove me mad. Anyways, the solution is quite simple, once you know how to do it. Anton Holmquist has a short, to-the-point blog post about it, which I wish I'd found earlier.
The one big drawback about this method is, like you pointed out, the limited uniform space. For those who don't have a clue what that is (like I did): it is the space available for declaring uniform variables in the shader. I read somewhere that this space relates to the amount / size of registers the GPU has - correct me if I'm wrong here. For anyone interested, calling glGetIntegerv(GL_MAX_VERTEX_UNIFORM_VECTORS) will return a number that says how much uniform space you have on your system. The specification for OpenGL ES 2.0 says it has to be at least 128. The number is expressed in vectors, and since each matrix has 4 vectors, that means you could declare a maximum of 32 matrix variables or, in my case, two arrays of 16 matrices. In other words, I can batch a maximum of 16 cubes now.
Dynamic indexing has certainly improved performance, but I am not entirely happy yet. I will implement the abovementioned option 1, hoping to improve performance by shifting work from the GPU to the CPU and, as a next step, parallize the move() and draw() operations.