Seagull BagsI bought a Standard Large from them when I went car-free two years ago and can't say enough good things about the bag and the company. Comfortable, spacious, waterproof, DURABLE (would look brand new if I bothered to wash it, and I use it 6 days a week), made in Columbus OH, excellent customer service, not really any more expensive than similar options from Timbuk2 and other larger companies. Size L is just right for carry-on luggage, and it's pretty much all I travel with.
It's not really made for walking. The asymmetry of any messenger bag will mess with you after a few miles. But it's still better at that than anything else I've tried. If you ever want to use it to walk more than a few miles, get a backpack (which Seagull also makes, I don't have one but they are recommended by a few of my friends who do)
You'll probably want something smaller than what I have, looking at what you want to carry... maybe a medium