When you bake, try separating each UV island into a separate smoothing group. That usually fixes baking issues like that for me. There are usually scripts that do that for you.
From the looks of your images, you have numerous hard edges running throughout the inside of your UV shells. Soften these edges, and make sure only the UV perimeter edges are hard. As pior said, it's not absolutely necessary to have hard edges at UV seams (it can cause issues with mip mapping in some cases), but for the…
Triangulate your model before baking and before importing into your engine. You have no way to know how each export/import procedure is going to interpret these diagonals, therefore you do want to force them every step of the way. The very first picture in this thread is typical illustration of this problem, and this might…
With Maya, when you're baking in Maya, triangulating before you bake really isn't necessary for any reason. What you do want to do however, is lock your normals and triangulate before you export(because triangulation in Maya changes your mesh normals). If you're sending your mesh to an external app like Xnormal to bake you…