I have had the best luck with Avocet Cross tires. They roll reasonably well on the road and can handle sesnible off roading. Even on a loaded bike, I've had them last over 3000 miles. They have a very thick tread so they are difficult to puncture. You can also find them in many widths; I generally use 32s or 35s. They have a squarish profile so spirited cornering on them can be an adventure as the bike goes abruplty from very little lean to a lot of lean.
Some things to consider is how much off-road riding you will be doing, if any, and how much weight you are carrying. The general rules are the more off road riding, the more tread you want, and the more weight, the wider the tire should be.