For your transatlantic crossing, try to get an American airline (CO DL or NWA) rather than the European partners (KLM AF) who seem to charge much higher taxes/fuel surcharges.

Be prepared to be creative with your routing - if you cant find availability say Paris-New York, try Paris-Atlanta (with DL) in business, then ATL-LGA.

Also, when doing searches use NYC for New York rather than JFK only or EWR only