As of NCR, I know three companion spots...they hang out inside Dusty's cantina by one of the chairs, to the immediate left of the door to the Rawhide Saloon, or in the table surrounded by chairs in the bazaar(next to iguana stand).
In junktown, they are in the bar next to the south gate, as well as by the dog salesman near Gizmo's casino.
In the Hub, I know that they wait in multiple places inside the maltese falcon, or in front of Mitch of the all-in-one store.
In the Den, I saw some in Becky's bar, either in front of the counter or between the tables.
I have heard rumors of San Francisco train station, but it is not verified.
Hope this helps people, I will keep updating when I find new things.
Also, something you may want to note, the travellers are balanced out in stats. High Hp ones often have bad stats. Low hp ones usually have higher stats. The only ones that seem to matter is strength and perception for accuracy, agility for AP, and endurance for level up HP gain. Of course, you could have a 5 ap thrower with 86 hp who cant aim and doesn't have enough strength to throw beyond his face. The way I see it is their stats are randomly forumlated, and their highest combat skill becomes the "tagged" one. So one could have a high intelligence, charisma, or luck, and low everything else, compared to a 218(highest I found so far)hp with 10 ap, 7 st, 6 pe, and 1 int/ch.
