I believe how much you pay depends on the airline carrier and origin of departure and arrival. Canadian airports, especially YYZ, and LHR are notorious for high airport fees so any departures from those airports you're already disadvantaged.
After that, like many experienced FTers here, they know AC, LH and a few other airlines have a very high fuel surcharge. So if you book any of those airlines from a departure airport with high fees, you're doubly disadvantaged.
What remains is how willing are you to make connections and how selective are you on airlines. If you like to fly European carriers out of NA, US cities often have more J/F availabilities (there were last minute F seats on LH from NYC to MUC!)
Most people use the UA MP reward search site and the *A search site to check for routing combinations and availabilities. You can then call AC to feed them the itinerary. Unfortunately they will tell you they won't know the total fees 'til you issue the ticket which sucks.
IMO AE points are good for short haul flights (15K RT) cross-border, and mini-RTW in J/F on low-fee charging carriers. Anything else is a waste of points. Of note, I would also say AE points are good for *A upgrades when available, 'cause theres ZERO fees/scamcharges added. Just used 45K to go from J to F on OZ FRA-ICN with no fee. Could've gone M fare to J on LX 87 YUL-ZRH for 20K but J cabin sold out. From a M fare to J for 20K no fee on LX is worth it in my opinion. To try to get 100% status miles on the lowest possible Y fares I fly UA, LX and SQ almost exclusively, plus AC of course for Eupgrades.
Since living in NYC now I've been accumulating UA points on my Visa to use for upgrades and reward travel (no status in UA, no point in getting status with them) and getting AE points for status and redemption for mini-RTW for my family, trying to strike a balance with best of both worlds.