I used the large Sturdibag with my dog when she was a puppy. Unfortunately she's outgrown it (though she can still fit, she's just really cramped), so we sized up and got her an XL Sturdibag.
We traveled with her NYC-Paris in her large Sturdibag. She was about 5 months at the time. I highly recommend the bag; it's really lightweight, has a pocket with zipper which is convenient for any paperwork, and also has windows and privacy flaps. At the time that we traveled (last year) our dog was about 13" tall and weighed about 10 lbs. (She's now 17" tall and weighs 15 lbs).