CabSense is an app available for both iPhone and Android phone that uses millions of pieces of actual cab data to analyze the best place to find a cab in NYC, in a particular location at a particular time.
Their press release says that they use an algorithm based on 90 million taxi rides to calculate each corner in the city in terms of how easy it is to find a cab there. So it can use your current location, and your current time (or any location and time you choose) to let you know the best place to stand and hail.
I came across a hidden extra by accident–if you shake the phone, the screen turns into a flashing light and whistles, to help you get that taxi.
And it’s free.