Why don't you test people and figure out what they would be easier to use for them?
I suspect that Country - city - services would be the way to go but the best thing to do is to put it to the test. Whatever is easier to use, that would be the way to go
Before asking, do a search... if you don't find the answer, then ask The purpose of this forum is to help others in the community, that's why it's called Sitepoint and not Linkpoint. SP Guidelines - No fluff.
What version of phpLD are you using?
I know there are some state category dumps out there that might help to get you started.
But yes if it is world wide...I would concentrate more on the what it is then the where it is. So hotel category, ticket category and then make it mandatory that the listing put their address in.