I'll answer the questions first, and i'll post the code at the bottom.
how many triangles does a 128x128 heightmap
i'm not quite sure exactly how many....to get an idea i did a random terrain genoration in a 3D modeling program, except at 64x64, and it was upwards of 7000 triangles...so....alot 
Do you have backface culling on?
yes, but it dosn't appear to make much difference on the framerate.
What does the third dimension of the skybox represent? I thought most typical skyboxes are just 5 2D quads, or a half sphere or something similar (this is just a question to help me out).
My skybox is 6 2D quads put together to form a cube. The 750x750 is length and width, and the x400 on the end is the height.
now the last few questions you had are better answered if I post the code, so here it is:
FPS calculation (Time Based):
Code:
float g_FrameInterval = 0.0f;
static float framesPerSecond = 0.0f; // This will store our fps
static float lastTime = 0.0f; // This will hold the time from the last frame
static char strFrameRate[50] = {0}; // We will store the string here for the window title
static float frameTime = 0.0f; // This stores the last frame's time
float currentTime = timeGetTime() * 0.001f;
g_FrameInterval = currentTime - frameTime;
frameTime = currentTime;
++framesPerSecond;
if( currentTime - lastTime > 1.0f )
{
// Here we set the lastTime to the currentTime
lastTime = currentTime;
// Copy the frames per second into a string to display in the window title bar
sprintf(strFrameRate, "Edit Window | FPS: %d", int(framesPerSecond));
// Set the window title bar to our string
SetWindowText(EditWin, strFrameRate);
// Reset the frames per second
framesPerSecond = 0;
}
Program Main loop:
Code:
// program main loop
while ( !bQuit ) {
// check for messages
if ( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) {
// handle or dispatch messages
if ( msg.message == WM_QUIT ) {
bQuit = TRUE;
} else {
TranslateMessage( &msg );
DispatchMessage( &msg );
}
} else {
g_Camera.Update(); //update camera
ProjMatrix(); //setup projection matrix
g_Camera.Look();
ModelMatrix(); //setup modelview matrix
glClearColor( 0.0f, 0.0f, 0.0f, 0.0f ); //clear screen to black
glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); //clear buffers
glPushMatrix();
DrawTerrain(0); //draw terrain
CreateSkyBox(g_Camera.m_vPosition.x, g_Camera.m_vPosition.y, g_Camera.m_vPosition.z, farclip + 1, farclip + 1 , farclip/2 ); //draw skybox
DrawCrosshair(g_Camera.m_vView.x, g_Camera.m_vView.y, g_Camera.m_vView.z, TRUE); //draw crosshair
DrawHUD(); //draw HUD
glPopMatrix();
SwapBuffers( hDC );
}
}
My code for rendering the terrain:
Code:
void DrawTerrain(int DrawWater)
{
glActiveTextureARB = (PFNGLACTIVETEXTUREARBPROC) wglGetProcAddress("glActiveTextureARB");
glMultiTexCoord2fARB = (PFNGLMULTITEXCOORD2FARBPROC) wglGetProcAddress("glMultiTexCoord2fARB");
FILE *pFile = fopen(filename, "rb");
fread(&heightmap, TERRAIN_SIZE * TERRAIN_SIZE, 1, pFile);
fclose(pFile);
for (int z=0;z < TERRAIN_SIZE - 1.; ++z)
{
glActiveTextureARB(GL_TEXTURE0_ARB);
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D, g_Texture[terraintex1id]);
glActiveTextureARB(GL_TEXTURE1_ARB);
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D, g_Texture[terraintex2id]);
//glActiveTextureARB(GL_TEXTURE2_ARB);
//glEnable(GL_TEXTURE_2D);
//glBindTexture(GL_TEXTURE_2D, g_Texture[0]);
glBegin(GL_TRIANGLE_STRIP);
for (int x=0;x < TERRAIN_SIZE; ++x)
{
// render two vertices of the strip at once
float scaledHeight = heightmap[z * TERRAIN_SIZE + x] / SCALE_FACTOR;
float nextScaledHeight = heightmap[(z + 1)* TERRAIN_SIZE + x] / SCALE_FACTOR;
float color = 0.5f + 0.5f * scaledHeight / MAX_HEIGHT;
float nextColor = 0.5f + 0.5f * nextScaledHeight / MAX_HEIGHT;
glColor3f(color, color, color);
glMultiTexCoord2fARB(GL_TEXTURE0_ARB, (GLfloat)x/TERRAIN_SIZE, (GLfloat)z/TERRAIN_SIZE);
glMultiTexCoord2fARB(GL_TEXTURE1_ARB, (GLfloat)x/TERRAIN_SIZE, (GLfloat)z/TERRAIN_SIZE);
glVertex3f(static_cast<GLfloat>(x - TERRAIN_SIZE/2), scaledHeight, static_cast<GLfloat>(z - TERRAIN_SIZE/2));
glColor3f(nextColor, nextColor, nextColor);
glMultiTexCoord2fARB(GL_TEXTURE0_ARB, (GLfloat)x/TERRAIN_SIZE, (GLfloat)(z+1)/TERRAIN_SIZE);
glMultiTexCoord2fARB(GL_TEXTURE1_ARB, (GLfloat)x/TERRAIN_SIZE, (GLfloat)(z+1)/TERRAIN_SIZE);
glVertex3f(static_cast<GLfloat>(x - TERRAIN_SIZE/2), nextScaledHeight, static_cast<GLfloat>(z + 1 - TERRAIN_SIZE/2));
}
glEnd();
}
if(DrawWater == 1)
{
glColor4f(0.9f, 0.9f, 0.9f, 0.15f);
glEnable(GL_BLEND);
glBlendFunc(GL_ONE, GL_ONE);
glActiveTextureARB(GL_TEXTURE0_ARB);
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D, g_Texture[16]);
//glActiveTextureARB(GL_TEXTURE1_ARB);
//glEnable(GL_TEXTURE_2D);
//glBindTexture(GL_TEXTURE_2D, g_Texture[0]);
//glActiveTextureARB(GL_TEXTURE2_ARB);
//glEnable(GL_TEXTURE_2D);
//glBindTexture(GL_TEXTURE_2D, g_Texture[0]);
glBegin(GL_QUADS);
glTexCoord2f(-40.0, 0.0);glVertex3f(-SEA_SIZE / 2, SEA_LEVEL, SEA_SIZE / 2);
glTexCoord2f(-40.0, 40.0);glVertex3f(-SEA_SIZE / 2, SEA_LEVEL, -SEA_SIZE / 2);
glTexCoord2f(40.0, 40.0);glVertex3f(SEA_SIZE / 2, SEA_LEVEL, -SEA_SIZE / 2);
glTexCoord2f(40.0, 0.0);glVertex3f(SEA_SIZE / 2, SEA_LEVEL, SEA_SIZE / 2);
glEnd();
glDisable(GL_BLEND);
}
if(DrawWater == 1)
{
if(g_Camera.m_vPosition.y < OverlayElevation)
{
WaterOverlay(g_Camera.m_vView.x, g_Camera.m_vView.y, g_Camera.m_vView.z);
}
}
}
You could post the exe and data so we could see if it runs crappy on our systems. I also have a p4 with an ati. Did you sayyou tried it on other computers or just your two? Although im pretty sure it really is code inefficiency and not your computers.
I only tried it on my two. If the code I provided dosn't help any, then i'll post the exe and the necessary files.
Hopefully the code will provide enough info tho, but if not, let me know 
-psychopath
