On the other hand, though, there’s a huge gap in the power level between feats, and I’m not sure I’d necessarily feel the same way if the feat chosen was Shield Master, which is one of the weaker of the full feats. I might also be more inclined to set aside a list of the more flavourful feats like Chef that the players could just get for free without the associated ability boost and let the players just pick one for free as character building.

On that, I agree and I've explicitly done exactly that. In hindsight, the option to boost a main stat with a "Ribbon" half feat to 18 was still a tad too strong, but that can be easily house ruled along the lines of

At character creation, every PC can choose a feat from (list). If a half feat is chosen, it's Ability Score Increase can't be used to achieve a total character creation Ability Score Increase of more than +2.