Amex offers a points bonus of 25% once you hit 10K in spend. Coupled with the 50% bonus at gas/grocery/drug, the points could add up pretty quickly. If I know they will exceed 25K in spend for a good portion of the year, I could make an argument to bump them to the Amex Plat version, which offers 1/1 up to 10K, 1.25/1 10k-25K and 1.50/1 for every dollar spent above 25K - and I believe you still get the 50% bonus for gas/grocery/drug on top of the above bases. The Plat cards also offers a free 15K 'short haul' companion reward each year, so they could both fly to NYC for free (not sure what taxes/fees go with AP rewards) every year - a value likely to equal the membership cost.

Maybe the Aeroplan and SPG cards are tied for best options? I'm still leaning towards AP because their travel is likely to be on AC, UA or *cough* US, and next year they can also fly CO as well. Right now they only fly once a year to Florida, but with a stack of miles, I can send them to NYC a couple times and even Vegas.