We have a Pro 24x24 with the NEA 23's and have had zero problems. It has cut anything I could have asked and probably much faster then I have it going now.
It is pretty easy to add "ballast/weight" to the Pro's given their open construction.
As far as the size, get as big as you can afford and have room for. The Pro's can be lengthened really easily but not the width so maybe go with the 5x5 to start. I know for us there are a lot of times I wish I had bigger, but just don't have the space.
We still run Mach3 with the 2010 screenset to automate the tool changes as much as possible. From what I can gather Mach4 doesn't quite have it yet but don't hold me to that.
The other thing you might want to consider is the cncdepot S30 BT30 spindle. I wish I would have known about it when I bought ours as I would have jumped on it. At least for me, tool changes drive me nuts, but the 2010 screenset has made it a lot better with auto touch offs.
And now you can easily add the 4th axis to the Avid machines.
I can't say enough about Avid customer support.