People who are under threat of direct and targeted violence can get a waiver for the public notice requirement of a name change and have the name change sealed (that is: not be available to anyone who does a public search). But to get this, you generally have to prove that you are personally and individually in danger (as opposed to belonging to a category that might endanger you). As far as I know, it is used for people who have been victims of violence, including domestic abuse and violence.
Rob: Depending on where you live, sometimes the publication requirement DOES include more information about the person (including, sometimes, an address).
Otherwise, publishing the name change is a pretty common legal requirement. You have to factor in the cost of it and the amount of time it takes (how soon can you get it published, how many weeks are required) into the process of changing your name.
And for everyone changing his (or her) name - note that just because you've changed your name legally, it doesn't mean that your old name will never be visible to anyone, esp for adults. Your old name will be linked to your credit scores, your DMV record, and pretty much anyone who wants to hunt down the info will be able to if they really care to try.