Character names are definitely something I agonize over, and I use everything from baby name resources, to phone books, to random name generators (often just looking for syllables I like), to census records from various locales (the census records make for particularly interesting results).
I almost never use a first name I find with a last name I find with it. I search until I find one name that sticks, and then search for its companion. Of course, if the names are at all common, someone has that name, but I never start out trying to pick the same name as someone else.
Even my main characters tend to change names over the course of my planning, and sometimes also over the course of my writing and even late-stage editing.
In a literal sense, the person’s name is all we can “see” of them, and so the name has a lot of connotations for how I picture a character. A Mary looks a lot different from a Tzer-Talan, even if you give them the same detailed physical description. Even a Pam looks different from a Mary in the above situation.
I’d say I agonize over the major character’s names just as much as the title (even though I know the title is probably going to change, I want it to be the best it can be out of the gate). The minor characters are less troubling, but still really important and often hard.
Sometimes, when I don’t have much planned for a character, I pick a name that evokes something interesting and then build the character up around that. An unusual character name can almost be as good as a writing prompt!
