Have you tried BI’s bias option, they look very similar to the common terminator artifacts found on spherical objects when they are not subdivided enough.
Use a subsurf modifier or, at least, add a loop cut in the middle. And, of course, use smooth shading. Flat shading on such a curvy surface… Really?
The subsurf modifier is really the easiest way, it will adapt to any shape and you won’t have to modify the shape by hand. You will however need to set the crease of the contour of the whole shape to 1 so that it doesn’t deform. Use [CTRL E] (Edge menu), [SHIFT E] (Crease function) or look somewhere in the [N] panel, I think.
This happens because quads are bend to two triangles. Smooth shading will fix the shading itself but shadows are still calculated from the raw geometry… As it’s been said, add subdivision surface. To preserve your outlines of the object, edge select them in edit mode and use CTRL E to make them bright purple
Also make sure that you have no duplicate vertices. Simply press W in edit mode and select Remove doubles. You’ll see if any vertices are removed in the top menu next to render engine selection.