Agreed, I prefer leather but don't want a heavy leather bag, that would defeat the purpose/benefit of the Air.
I do like Roots messenger bags but I wish they had a little grab handle sewn in so when it's not on your shoulder you have a way to carry it. I wish the Muzetto bags had a handle too.
Timbuk2 messenger bags come with a handle, or it's a $10 option to add it. Only problem I find with Timbuk2 bags is they're true messenger bags and their shoulder straps are a little shorter.
Price isn't a concern, but getting a (smaller) really functional bag is.
I just picked up this leather Tumi bag at the Tumi store in Rockefeller Center, NYC. I was using just a sleeve and needed a bag. So far I really like it, it fits the Air (I have 11.6" but should be fine with 13 also), notebook, iPad, chargers, earbuds, etc and even fits into the center compartment of my RedOxx Air Boss for one bag travel.
http://www.tumi.com/product/index.jsp?productId=4210134&prodFindSrc=paramNav
Good luck with your search.
-Ost