Average normals at vertices before exporting
The smooth button does it for you.
(Left side) Object Tools -> Smooth (under Shading),
Then when you go File -> Export -> Wavefront (.obj),
 make sure you click on the Include Normals checkbox.