Do you make people hard to deliver to have to pay more, or do you "average" out the cost and make everyone pay roughly the same amount?
With a combination of taxes, flat-rate fees, and delivery-distance based costs, I think it's more than possible to make a system where it's not "free" or extremely cheap to send somewhere hard-to-get, but it's also not prohibitively expensive.
And IMO the postal service is riding that line in a way that i'm happy with. I appreciate that I can send a small box across the country for $5, and I can do that whether I live in NYC or in middle-of-nowhere pennsylvania. And I'm more than happy to pay a bit more in taxes to make up for the difference that the flat-rate doesn't cover if it means that lower-income individuals won't need to pay as much to send mail at all.
I know that there are problems with not having competition, but I think mail delivery is along the same lines as other "naturally monopolistic" things like power, water, sewer, etc...