The main reason why brownies become mal-formed when you cut into them is because the pressure of the knife cutting in the downward motion AND the sticky brownie sticking to the knife and being "dragged" downward as it is being cut.
Generally to get a even nicely shaped brownie cube, the brownie should be baked well enough so that it is not gooey anymore. A lot of recipes are for "really soft gooey at the center" brownies that can become easily malformed. Make sure to bake a brownie sufficiently so that it is done well enough to hold its shape.
You should definitely let the brownie first cool. The cooling process allow the brownie to continue cooking and set. Most brownie recipe also factor in this cooling step into bake time. At that point, you should use a very sharp thin knife(to reduce the amount of pressure). In the past, I have tried the warmed blade method by placing the knife under hot tap warm. I then dry it and lightly oil it with canola oil before cutting into the brownies.
Another thing I've tried in the past is to let the brownies cool in the pan but when it was time to cut the brownie after cooling, I pop the brownie out of the pan first. This makes it easier to cleanly cut AND you will also avoid scratching your brownie pan. But becareful. This cannot be done for all recipes of brownies.
Lastly, as in my comment to your question, it would be easier to evenly cut the brownies into 16 brownies per batch. You would cut it 4 x 4 to yield 2.25 x 3.25 brownies. It is easier to cut 4 x 4 because you can cut down the center of the brownie and then cut down the center of each sides. It is easier to eye ball where the half line is rather than eyeballing how to evenly cut into 5 equal parts if you are doing 3 x 5.
EDIT:
According to your comments you decided you might go with the muffin tin method. If you do that, I would suggest instead to go with the muffin's relative, cupcake method. Just use cupcake liners to avoid having to deal with a large amount of nonstick spray.