To start with, it definitely sounds like you're on the right track by using the Spatial Autocorrelation tool to figure out a good distance to use for your Cluster and Outlier Analysis. Actually, there is a sample script in the resource center that does this analysis for you (and has a lot of documentation about how to use this method), which is called Incremental Spatial Autocorrelation, in the Supplementary Spatial Statistics Toolbox.
The output that you're seeing looks alright (without having seen your data). It isn't uncommon to see p-values that are all 0.00000. It means that at every distance you've tried you're getting statistically significant clustering. The key is to look for peaks in the z-scores associated with those statistically significant p-values which occur at a specific distance. Peaks in the z-score represent distances at which the spatial processes promoting clustering are the most pronounced. If you download the Supplementary Spatial Statistics Toolbox there is a folder called Documentation, which has a document that helps you Learn More about Incremental Spatial Autocorrelation. You can also find tons of other resources about the spatial statistics tools here: http://esriurl.com/spatialstats.
It is a free software and is really good. You can easily read shapefiles and there are good tutorials for Moran's I. Basically the steps are, calculate Weight Matrix, calculate moran I. You need to calculate the weight matrix before you can calculate moran I.