I've found private mailbox providers to be preferable in most every way to post-office PO boxes. Private providers are "street addressed" to begin with, virtually always accept from all couriers, usually have longer hours, often can call or email you when you receive a package, etc. In most cities, there are also more of them than post offices, I suspect because it's such an easy business to start. Look around your neighborhood: copy/print shops, shipping stores, and small business supply stores probably also rent mail boxes.

I wish this was an industry with a bit more visibility. When you think about renting a "PO Box", there's a good chance that you'd be better off with a box rental from a private mail service.