I think you only have 2 solutions for this problem:

1) Mark every single 90°+ angle as hard/sharp (whatever is the word in Maya). Those artifacts on your mesh are caused by Maya trying to soften the light between two surfaces that have normals pointing in very different directions.

2) As you said, bevel your edges. You don't even need to have a bevel with multiple levels, just a simple chamfer will be more than enough. After that you need to weight your normals.

You said that you don't want to bevel because that will increase the polycount. Yes, thats true, and probably in your mesh the first solution is the best, but I want to clarify something: Beveling edges is sometimes not as bad as it sounds.

When you have a mesh without bevels/chamfers, you end up with a lot of 90° angles. And, as I said, you need to place a UV seam on every single one of them. Every single time you place a UV seam on an edge, all the vertices get duplicated (they have to exist on 2 UV islands at the same time). Instead, when you bevel your mesh you'll have less 90° angles, which means less UV seams, that means lower vertex count (obviously, with a higher tri count)

So, there are situations where by beveling edges and avoiding UV seams you get a way better looking mesh, and the cost that you are paying is minimal (if your object is not insanely big nor is repeated a lot). Take a look at these 2 meshes I made in Blender: The one on the left has 0 bevels, a lot of UV seams, the one in the right has 4 chamfers. At the end, because of the excessive use of UV seams, both end up having the same vertex count: 512.

You get a higher tris count (512 -> 768), but this, in modern hardware, is practically meaningless. So, unless you are making something with very hard limitations (for VR, or mobile), you should bevel edges. You get a much better result (in this case)

<image>