I can only speak for the Roman world, but in that case, there was no formalized system in the Republic. Cicero's letters were carried by his slaves, clients, or, often, his peers. In the case of the latter, very often Elite homes were stop-overs for other elites along their journey. So a senator departing Rome might come for a stop-over at Cicero's villa in Campania on his way further south. In this case, the letter's delivery was at the whim of the bearer. Often Cicero expresses frustration that he does not receive letters regularly, or that there have been interruptions. During the crisis of the Civil War in 49, Cicero and Atticus were often writing three or more letters to each other per day, and Cicero mentions more than once that he has received letters all in a bunch, or out of order. He also mentions at least once that a letter-bearer had been robbed on the road. It was ad hoc, but it worked (mostly) just fine.

For addresses: they generally were not needed. There was much less anonymity in the ancient world. For the elite, no address was required. "Marcus Tullius Cicero at Formiae" or "Pomponius Atticus, Rome" was more than enough. In fact, that is how the letters are "addressed" as they come down to us. "Marcus to Atticus sends greetings." Of course, the original letters are long long long gone. We don't know how individual letters were packaged or addressed. Most elites had multiple residences. Cicero bounced back and forth between Rome, Tusculum, Formiae, Capua, and other places in the early months of 49, and it was up to the letter-bearer to find him.

For a person of less importance, there was still little anonymity. If you needed to send a bill to a person in another city, it was enough to know the person's name, perhaps his tribe affiliation, and generally where he was. So "M. Favonius the wine merchant in the Theater District, Pompeii" was enough. Once in the general area, every chatty local would know where to find Favonius.

Interestingly enough, there does not seem to have been a "courier" profession. If anybody would have had one and named the position as such, it would be Cicero. Instead, he just used whoever was convenient and perhaps also coincidentally going in the same direction. Elite Romans had underlings going all over the place for this or that reason, so it wasn't difficult to find someone in his house to take letters. For army commanders, there were cavalrymen or scouts available to take missives quickly.

You mentioned the Imperial post. It was set up by Augustus, as you said, but was mainly reserved for official business. You couldn't send a Happy Saturnalia to Aunt Aurelia from Britain on the Imperial rescript. It operated a lot like the pony express, with waystations and stables set up along the major roads. Private letters still had to travel ad hoc.

Peter White has a good write-up of letter-writing in the Late Republic (Cicero in Letters: Epistolary Relations of the Late Republic Oxford 2010).