From my understanding of it, you'd be better off with a BSP tree for indoor scenes and an octree for outdoor ones (terrain, that sort of thing). The downside with BSPs is that they take a fair time to compile, which means that you won't get much dynamic scenery.

I'll convert Nate Miller's BSP tutorial for you sometime soon (and perhaps the gametutorials stuff, if nobody has done so before -- maybe at Sulaco?). In the mean time, have a look here for BSP code (note that it's in Direct3D, not OpenGL, though...).

(Aside: Shining Force for the Sega Megadrive rocks. )