Yes, the personal "a" is needed in all cases that you talk about people.
- Debo/necesito/tengo que encontrar a mis amigos / a mi tío Eulogio / al conserje / a los niños / a alguien que me ayude / a toda la gente del barrio / a la comunidad de alumnos / al grupo de inglés...

Your both pairs of expressions in colloquial language mean basically the same (at least among the people I know), and I don't think we stop and think about the nuances. However, I'd say that "necesito" suggests that it's me who feels in need of doing something, while "tengo que" in some cases is more a demand from someone else or from a situation. "Debo" is quite compelling and it expresses both inner conviction and outside imposition (sometimes context separates both ideas).
As for "encontrar" and "localizar", they can be used indistinctively, but "encontrar" is more like being able to communicate with someone, while "localizar" is both to know where they are and to be able to communicate with them.
- ¿Ya localizaste a Juan? -> Although it can simply mean "have you found him?", it can also mean "do you know where he is?" and "have you talked to him?"