What you are seeing is normal, no pun intended. I'm surprised that you are not seeing at least some improvement by normalizing the normals in the fragment processor.
You can either increase the detail of the model or you can post your shader code. There are several people around who can help you configure your shaders to perform better, both visually and computationally.
Also, normal mapping will resolve this issue. For dynamic height mapping you'd have to use a tangent space normal map. (Unless someone came up with something clever that I'm not aware of). Most people only use tangent maps anyways.
There is an example in the cgToolkit from nVidia that shows how to use a normalization cube map to align the tangent space normals to your models' geometry.
In the installed directory look for: /cg/examples/OpenGL/basic/23_bump_map_floor. It will easily port to HLSL or GLSL with no issues.