For one, this is why we have normal maps. You can bake nice normals at a super high poly resolution. Your real issue is just not enough edge loops.
Anytime you have a vertex that is on an edge that is 90 degrees, or close to it, you need to create loops around it, otherwise it is interpolation lighting over such high angles. Also, this is why you usually apply sub surface division and then back normals onto low poly meshes. For this same type of reason. More polys = better surface representation and lighting.