Carrying letters is rivalrous. As more people send letters, the bag will fill up and more mail carriers will be needed.

Compare this to a real public good, e.g. national defense. National defense is non-rivalrous because me enjoying living in a non-communist country does not hinder you enjoying the same thing.

As for the postman being a romantic figure, not sure how that fits into the question of whether mail delivery is a public good or not.