Just bringing the conversation here 
For my 3 most important characters, I have a general idea of their physical appearance, and some family history. (Along with their first names of course)
Part of the problem is that the story takes place in a fantasy world though, so there aren’t really direct equivalents ethnicity/nationality wise, to be able to look for surnames based on origin. And the characters are all from the same kingdom, (though for one of the characters, his family line is from a kingdom that was essentially conquered and absorbed, leading to frequent rebellion)