Frying is certainly the tastiest way to enjoy gizzards. But it does somewhat negate any healthy aspects. And frying doesn't do much tenderizing.
I would whip out my trusty pressure cooker. I'll bet 15 - 20 minutes at 15 psi would do the trick.
Better yet, set your timer to 10 minutes, cool/remove from pressure cooker, then flour & fry them. I'm getting hungry thinking about that option.
Tom