Given my experience (CS PhD. CMU) I would say that you are likely a very good candidate. The PhD you left was pure-math (not CS) so I don't think it counts much against you. You have lots of plusses (analytic and work experience) and the best thing would be to be very articulate about what you want to do (at this point they will be expecting you have some goals). The CS GRE really can not be taken without some studying (it had some obscure stuff on it when I took it).
Now for picking a grad school a lot of things are really important.
1) Will they fund you?
2) Are they teaching what you want to learn?
3) Is it a happy place?
Don't want to start a fight here- but schools vary by A LOT on these criteria.
I strongly agree. The PhD is an apprenticeship, so the people you'd be working for (and with) are the most significant factor. Make sure you fit with the research and social philosophies of a program before applying if you can, and certainly before accepting an offer.
As you leave school and prepare to enter industry or academia, my experience has generally been that the strength of the recommendations backing you matters far more than whatever rank your institution may have.
As you mentioned AI/machine learning, I believe these factors are even more important. There are some very distinct schools of thought when it comes to those things, so make sure you look for philosophical compatibility when picking programs. AI has a few deep schisms and widely separated sub-fields, so tread carefully.
It may be worth it to consider some of these: What's your philosophy of mind? Symbolic/statistical/neural? How important is biology/neuroscience when looking at artificial intelligence? What general approach to AI/machine learning most interests you?
Now for picking a grad school a lot of things are really important. 1) Will they fund you? 2) Are they teaching what you want to learn? 3) Is it a happy place?
Don't want to start a fight here- but schools vary by A LOT on these criteria.