In 14th-16th century England, how would a normal person get an urgent message to someone in a different city reliably?

To get a message speedily across the country you would most likely hire a courier or messenger if you were wealthy enough, for added speed you would have a fresh horse waiting for the messenger at coaching inns (with stables) along the route. For example the messenger who traveled from Elizabeth I of England's death bed to tell James VI of Scotland that he was to become king did so in about a week, changing from his tired horse to a fresh horse at each inn on the route.

For more humble people less is known, as sadly it is only the stories of the rich and powerful that tend to survive. The London mayoral rolls (records) and trade rolls (records) show that merchants and the like regularly sent messages between key cities like York, Bristol and London. Bishops and clergy also frequently lived in and visited cities like York and London to be near their Archbishops and would communicate back and forth with their rural and small town parishes.

It is entirely plausible that those wishing to send messages to less urban ares would pay a fee to get messages sent to destinations via the clergy or mercantile classes. In many cases these messages would trade hands in coaching inns to other travelers going the right way. St. Albans grew as a town as it was on the outskirts of London and news, criers and travelers would rest there, and mail would change hands there.

In consideration of addresses, In small communities you would know most individuals by name, though in larger cities a description of the area the individual lived, a description of the person, the trade of the individual, the master of the individual (they could be an apprentice or a servant) and sometimes the geographical birthplace or country of origin of the individual would be used (e.g Welsh John). For most ordinary people this would have got a message into the right hands.

An example of this could be: Welsh John with the odd ear, apprentice to Master Robert Smith, Blacksmith of Cheapside, London.

The gentry, wealthy, clergy, government and the royal household however tended to have mail sent to an address (for example the Guildhall, or Westminster palace) with the recipients name or rank clearly labeled.

An example of this would be: The Lord Mayor, Care of the Guildhall, London

Hope this helps! If you want to know any more or have any other questions I will try my best to help out, I'm enjoying it as it means I can actually use my degree for something!