To be completely honest, during my first play through, I came in with a mindset of dominating every gym battle within at most 3 tries due to how easy the canon games were.
Thus, from that perspective, the hardest was the first gym.
After the first playthrough, players tend to prepare pretty adequately, with a full party asap, and then adding rotational members after the first gym decreasing the difficulty for a lot of the bosses.
I'm almost done with my 2nd playthrough now, and I almost miss the frustration of having to re-challenge a gym for the 9th time.