Just to make this a little less vauge, I will base everything on the Mercedes Benz American Express (MB AMEX) card, which is the closest to a $100 annual fee I found on American Express's website.
The benefits of a card with an annual fee generally are worth the cost if (and only if) you spend enough money on the card, and avoid paying interest to offset the benefit. Using the MB AMEX card as a reference, it offers 5X points for Mercedes Benz purchases, 3X points at gas stations, 2X points at restaurants, and 1X points everywhere else. Even if we only make purchases at the 1X rate, it only takes charging $10,000 to the card in a year in order to make up the difference. Not too hard to do on a card someone uses as their main method of payment. Every dollar spent at the higher rates only makes that easier.
There are a number of other benefits as well. After spending $5,000 on the card in a year, you receive a $500 gift card towards the purchase of a Mercedes Benz car. For anyone on the market for a Mercedes Benz, the card pays for itself multiple times with just this benefit.