If you are near one of the passport offices in the counrty (list over at http://travel.state.gov/agencies_list.html) that is probably the easiest way, call, make the appointment, show up with everything you need, and get it the next day.

I live a mile from one and work two miles from another, so I have never used one of the services, sorry.