I'd recommend something with 2 text boxes - source and destination. Using Google Maps api (or something similar) you should be able to convert this to a valid address (use ajax to do this as they type). They click submit, and see all of the different shipping options and prices. They select one, pay, print, and done.

I'd pay a little bit extra over the retail prices, not sure how much though. Especially if you get bulk discounts, you should be able to keep the mark-up pretty low.