I'll add another few nuggets that I noticed gave me a speed increase on the 2G (I tested a lot of permutations on 2G to know what was feasible).
- use shorts for indices if you can, or in general, experiment with vertex formats.
- experiment with tile sizes. 16x16 tiles may or may not be faster. CPU overhead differs little, data uploaded is more, but cache might be better utilized. As below, I wish I had my tests handy (and organized)
- use as short a format as you can for texture coordinates. I found it was faster to have shorter format and do the multiplication of the texture coords by the texture matrix.
- Test different screen formats. I don't have my tests at hand anymore (I gave up on iPhone aeons ago), but texture depths and display depths/orientation made for all kinds of different performance stats (logical but still, try it).
The biggest thing however, make sure your game is framerate independent. I never tested on my 3GS, but on the 2G you will get spikes. Even in a very tight, always the same testcase (just scrolling 4 layers), there was a 8ms spike every second or so.
As for plain C optimizations, the same goes as pretty much anywhere else. Memory layout, avoiding dynamic allocations, avoiding unnecessary branches.