I vividly remember the last time I used a payphone like this calling my then girlfriend (became fiance, became wife) outside a 7-11 in rural virginia before the turn of the century. Nostalgia by the bucketful.
For those interested, Citizen Engineer (http://www.citizenengineer.com/) did the same thing a few years ago. The video was produced by Phillip Torrone and Ladyada, and includes additional notes.
I recall needing to insert the proper toll into the payphone before dialing a number. He's added some instructions to work around that old limitation, so you can dial the number first, then insert the coins.
As much as I hate recommending the USPS for anything, they actually provide an official search tool for this on their site:
https://www.usps.com/locator/ (collection boxes > Blue Boxes)
The only thing I like about USPS is my mailguy, who is always smiling when he rings our doorbell on occasions when we have a shipment from Amazon and it's too big to fit in the mailbox.
He never fails to brighten the day of whomever greets him at the door at our house :)
Well-seasoned fifty pound familiar vintage steel vault pay phone, with a cell inside, VOIP-ing on your own or any open wifi. Running Redphone, or Silent Circle app, label it SECURE and.... and paint it red.
If you can get your hands on (or build yourself) a red box [1], you could even hack your own hack.
[1] http://en.wikipedia.org/wiki/Red_box_(phreaking)