If I have to confess, it took me hours... to choose a suitable bag for my 13" Air.
It's insane, but no matter how hard I looked, there was no bag out there that could match the elegance and simplicity of the Air. I had to settle with something that was barely there, but not quite. And it's coming next week to boot. So "hours" sounds like an understatement at this point.
What bag did you end up getting? I too spent days and days researching for the right bag and sleeve. I even returned a neoprene sleeve because I didn't like the lip that I had to pull open to get the Air in/out. I also had my mind set on a messenger style bag, but after research, went with a backpack.
I ended up with this combination, and am very happy: