Inov8, Montrail, Salomon, Lowa, Garmont, New Balance, NIke, and Hi-Tech all make excellent trail shoes. More important than any other factor is how well they fit you. And I don't have your feet to try out and tell you what shoes would work for you.
I'd recommend sizing your shoes about a half-size too big for city wear and taking a spare pair or two of socks that are all shaped differently. Your feet will swell up on a long trip (you know that) and having thinner socks to give you more room can be a tripsaver.
Try your shoes out on shorter trips and for goofing around in the park before taking them on a serious trip. One nice thing about trail shoes is that a pair that won't work for the trail probably is still fine for wearing back home. Kind of a multi-use item in life.