When talking to the travelers does the zone you encounter them in matter? Also does their dialog change if you talk to either the male or female ghost traveler first?
No, it doesn't. The speeches will be the same regardless of how many of the other character you've talked to or what physical order you find them in. Each time you find a new traveler you'll see the next dialog for that traveler. All travelers can be found in any order.