What are some practices for getting a name change so that people can find me more easily?
I think people stress too much about the "what if people can't find my papers?" problem. That's what CVs are for. Don't overestimate how often people will actually try to find all of your papers outside of hiring situations. It won't be often. By the time you are established enough to accumulate a significant number of publications, you will be connected to a research university or institute which will make it easy to link you to your publications. 

If "the vast majority of your connections will be people who only vaguely recognize/know you" you've got a problem that changing your name will not solve.

I'd especially like to hear from someone who have had this cause a career problem. My (legal) first name is one of 10 most common, and my last name is in the top 20 (within the US). While this is annoying, it has not caused me any career issues.