As a serial Villager I have long maintained that Battle is great for exploration. This is due to the simple fact that most Area Explore areas are no-recall, no-teleport anyway, so this completely mitigates the biggest drawback that a Villager has. Each Battle path has skills that are tremendously helpful during exploration, with the clear edge going to Defenders.

The biggest issue to keep in mind when playing Battle is that you're going to die. There are situations that a level 11 Elf Invoker can get out of easily that will kill you if you are Commander of Battle. That's the price that must be paid.

That said, as Daevryn pointed out, all areas can be walked out of. It's just a matter of having either someone who knows the way or bringing enough food and water to figure out the way yourself. While there is something to be said for the second approach, I would greatly recommend the first tactic as a way to learn an area.

It can be extremely helpful, as a Villager, to have friends who are Outlanders, as they can grant you Windwalk, which can get you out of some "I can't fly, I'm dead," situations.

As for priests, like Nep said, as long as they don't commune on you, everything should be fine. Obviously, priests of Twist will not make good travelling companions. Some other patron deities will find their followers at odds with Battle as well. Paladins, however, make great groupmates, as they can still perform first aid on you, which is a skill, not a commune.

Good luck.