Here are some changes that gave me a significant frame rate increase of about 10 fps with random objects disabled. The interesting thing is that these changes aren't in the main loop but are in tile loader. My guess is that I've reduced the memory footprint just enough to reduce CPU cache misses, though I have no hard evidence of this.
Initially I modified all SGBinObject member functions to pass/return by reference instead of by-value. This gives little or no speed up but allows for some optimizations in fgBinObjLoad(). It is these changes that reduce the number of memory allocations. Needless copying of vectors, and vectors of vectors, can be very memory intensive, especially if they are large.
Anyway I would be interested to see if you get similar results. I would emphasize that the frame rate increase only occurs with random objects disabled. I lose about 10-15 fps on my GF2MX 32MB with random objects, probably a fill-rate limitation or texture memory thing.