Ensure Visio new Connection Points at the middle distance?

There is no easy way of doing this (Or I just don't know a better way). Right Click on the Shape and select Show ShapeSheet. Now in the shape sheet go to the Connection Points Table and add manually your connection points and there coordinates.

Here is a simple example I made. This is a Rectangle from the Basic Shapes and I want to add a connection point positioned exactly in the middle of the two connection points which are already available by default. So I make a right click on the table and select Insert Row and then add the Width Value of X as 0.25 because it is the half of 0.5. And I add one more connection point with value 0.125 because it is the half of 0.25. Now I have two new connection points added exactly as you wanted.

For other shapes like for example the Ellipse you will need the help of Geometry or Mathematics to find the (X,Y) coordinates. It depends on the Geometry of the shape how the Mathematical equation will look like and how hard it will be. But you can ask these mathematical question here.

I haven't found an actual command in Visio 2013 to auto-align connection points, but the following work around should provide the results you need:

Bring up the Snap & Glue window (Alt+F9) and ensure the Snap option (under Currently Active) along with the Grid option (under Snap to) are checked in the General tab. The shape's connection points should now snap to the grid. This will allow you to align and space the points as required.