Given the results we've gotten so far I went ahead and came up with an algorithm that generates a "chunk" of 8x8x8 cubes with no inner faces. I say "cube" but each part of the overall chunk is no longer a cube persay, but an object that is capable of creating only the faces (which are planes) that it's instructed to. So an inner cube has no faces at all where an outside one has 1-3.
Previously I was creating (8^3)*6 faces = 3,072 faces for a chunk of this size. Now it's (8*2)*6 = 96. However, after plugging this back into my dynamic terrain generation and generating about 15 chunks I was disappointed to find the FPS dropping quickly. 15 chunks is about 1,440 planes, half of which are back culled, which I would assume can be rendered quite easily. My computer isn't too old.... Core 2 Duo @ 3.0 GHz, 4 GB RAM, modern graphics card, but I get about 30 FPS.
Are these results typical? I tried reusing the same plane and compiling it like we discussed above, but the results were similar.
Edit: I want to thank you again for looking into these issues. I'm a professional developer but don't have a lot of experience (yet) with graphics. It really is a whole new set of challenges.