"Am I wrong in my understanding that fuel cells actually generate electricity, then?"
Yes, you are wrong. Creating Hydrogen by reforming natural gas isn't efficient, but it is is far more efficient than using any form of electricity to electrolyze water into H2 and O. Both methods still take power to compress the Hydrogen to around 240 bar to load into a FCV. The fuel cell isn't 100% efficient either so the whole system is leaking energy from every step.
Hydrogen isn't a "fuel", it's a storage medium similar to a battery. One upside to EVs is that electricity is prevalent everywhere and Hydrogen needs to be captured and filling stations built to handle it. An EV is also source agnostic. It doesn't matter to the battery if the electricity was generated at a coal fired power plant or a wind turbine or even a petrol powered emergency generator. If the power is out in an area, a Hydrogen filling station isn't going to work either.