The nearest we get to the modern meaning in Shakespeare is in The Taming of the Shrew (III.i.59), when disguised Lucentio addresses disguised Hortensio: "Are you so formal, sir?" Here formal means punctilious, or stiff. A similar sense of outward show is present when Brutus tells his colleagues to act "as our Roman actors do, With untired spirit and formal constancy" (Julius Caesar, II.i.277). Here it means external or surface.
But in other contexts we see the earliest meaning of formal, from the late 14th Century, where it simply meant "pertaining to the form of something" - in other words, identifying something as being in its normal or complete state. So when Cleopatra says to a Messenger, "Thou shouldst come like a Fury crowned with snakes, Not like a formal man" (Antony and Cleopatra, II.v.41), she means like a sane, rational person.
David Crystal is author, with Ben Crystal, of Shakespeare's Words, published by Penguin