Don't make them all the same pattern.
The one I see most often is that they are Name the Adjective. All of them. At the very least, some would be Adjective Name. Little John. Fat David. Red Robert. More likely they would be varied by locatives -- John of the Woods, Jack under the Mountain, Sally Meadows -- and occupational references -- Alice Webster, Wilma Alewife, John Smith -- and patronymics -- Roberta Robin's daughter -- or even matronomics, even in a patrilineal society, if the father is unknown, or the mother is higher ranking or has the more forceful personality so she's the one people think of, or just has the more distinctive name -- Robert Maud's son.
And when using the adjectives, they tend to go for the obvious, not the flattering. Calling a man "John the Loyal" is unlike; "John the Lean" is more likely. And they were less hypersensitive to slights. As witness one Chinese informant who was flabbergasted that a sociologist thought he might object to being known as "the stutterer." He stuttered. Why wouldn't they identify him so?
Also, they change. There's one historical character who in his own time was known as "William the Bastard" and "William the Fat" as well as the one that is generally used in histories: "William the Conqueror." (It was the middle one. "Bastard" was youthful, and "Fat" was old age.)