http://www.pettravel.com/airline_rules.cfm
I don't know of an airline that will allow non-service dogs out of their carriers in the passenger cabin. I have seen pets in carriers, but it sounds as if yours is too big for that treatment. The service animals I have seen lie peacefully at their owners' feet and cause no trouble at all, but they never "sit on the seat next to" their owners.
I'm afraid I don't know what a "smaller regularly scheduled charter not usually found on Expedia and such" might be either, especially on longhaul routes such as NYC-Paris. If you are of means, you might consider NetJets:
www.netjets.com