That sounds like you are averaging the previously averaged result added to the new normal, which is wrong as it will always be biased towards the newest triangle.
Currently, every time I make a new triangle, I calculate its normal and then add that normal to the existing normals of the three vertices involved. After making all my triangles, I reduce the length of each vertex's normal to 1. I've also tried adding them and then dividing by the number of triangles involved, but that doesn't work and it doesn't sound like it should work, either.
ie. assuming A is the first normal, B is the second, C is the third (already normalized)
N = ||(||(||A||)+B)||)+C||
where as what you want is ||(A + B + C)|| so that all 3 have equal weighting.
The other one is that if you want a hard edge, then you need to split the vertices. The triangles in the shading are due to linear interpolation across each triangle, as the normals are stored per vertex not per face - you will never get just the edge highlighted unless you have incredibly high tessellation if you use smoothed normals.