Well let's start with what to me is the defining pair of names in S&S: Fafhrd and The Gray Mouser
One is a given name, one is a nickname, and you can use either technique or both.
Going back a thousand years, people rarely had surnames. They tended to have a given name and some other means of identification, often a nickname. Before Hastings, William the Conquerer was often called William the *******. In fact Edward III was the third Edward in a row, so that was also his nickname. Nobody actually called them Plantagenet. His father was Edward of Canarvon and his grandfather Edward Longshanks.
So we have nicknames, numbers and placenames. I admit numbers other than indicating lineage tend to be more in SF than fantasy, but The Prisoner comes to mind, and I recall the film Zulu, where so many soldiers were called Williams, they referred to each other by their military numbers like a forename.
We can look back to the origin of modern names and work backward to give an old feel. In feudal times people were often named after their jobs, which they handed down to their offspring. Fred the Miller, Johnnie the Walker, etc. Names like Johnson, are just formalized patronymics, so you can use son of or daughter of. There are foreign versions, the suffix -dottir is Icelandic, and there ben (Hebrew) or bin (Arabic), etc. Just Google patronymics or matronymics for different forms from around the world or make up your own.
And of course you combine these, eg. Much the miller's son.
Then there's naming after the flowers and animals of your world, eg. Paul Muad'Dib.
You can add in indications of nobility, or otherwise. Von is a Prussian indicator of nobility, although it originally just meant from, and I'm pretty sure that's where Bujold got Vor. If you have a caste system, you add that type of thing in too (like Cohen).
You can name them after religious figures of your world. There are quite a few Jesus's and Marys out there, and many more Mohammeds and Fatimas. Perhaps in your world characters take on the name of the god they worship to show dedication.
I suspect, apart from the religious naming, I've used all of these.
Despite my using Muad'Dib as an example, I also would vote against the general use of apostrophes.
Edited to Add: Just remembered another class of "names" I haven't yet used much, but mean to: those that are almost titles or relationships, but are used like names. There are equalizers, Brer Rabbit, Comrade Stalin, Citizen Robspiere. And names of respect: Goody, Reb, Father (when not given to a clergyman - Abu is a version). Shakespeare used Nuncle like this, IIRC. I called one fantasy character Old Man Evans, which is along these lines.