That particular issue looks like its the result of your smoothing groups / vertex normals (or whatever the equivalent Maya terminology is). Adjusting those settings would make pretty quick work out of it in Maya; unfortunately its not the 3d program I use so I wouldn’t be able to list the specific steps involved.
Is there another workflow that would allow me to create a low-poly mesh from a high-poly mesh with polypaint data? Otherwise, it seems like a lot of work to have to go in and clean up the seam manually because I need this workflow for hundreds of objects.
Polypaint can be projected between different meshes (tool: subtool: project all), so as long as you work on a duplicate subtool then it shouldn’t need to be preserved during the retopology stage. Depending on what you’re doing with these models shader-wise, the lowest subdivision level or a zremesh pass should quickly get you a cleaner mesh, with the rest of the detail being recreated through the texture maps.
This also means you could also use decimation master without needing UVs. Under the preferences you can have it use and keep polypaint data, which would preserve the vertices necessary to maintain the same quality of vertex colors. You could also scrap polypaint and UVs altogether. Just decimate a duplicate subtool, give that result a brand new set of UVs, and either project the polypaint over or use something like xnormal to convert it to a map.
As for wireframe cleanliness, triangles themselves aren’t the problem for a realtime asset; but long super thin ones can be. They wind up being so small that they contain few pixels (especially when 10-20 could be fighting for the same pixel in places), which can lead to hits in the fill rate.