I hear your concern!! I traveled with Bobbi and he was small enough to fit comfortably under the seat-BUT my toy poodle was not.
She did travel with the baggage and was fine-but I was not comfortable with that. They tag the carrier and give you a slip. When you get off to exchange planes or arrive at your destination, your baby will be right out the door of the plane with someone.
You have to take the weather into consideration too.
I have traveled Delta, Continental and this last time U.S Airways. It was 80 bucks each way in cabin and 100 bucks if they travel with baggage.
Good luck!