Galio sucks because he struggles too much in early game from auto attack harass .
Galio is pretty oppressive in the lanning phase. Most Galio's I've run into just take complete dominance of the lane.
Also - Galio is one of the very few CC-heavy tanks that can actually lane, and lane very well. Most CC tanks are forced into the support or jungle position so they don't get poked to death with their weak early, and so there CC actually means something via an ally capitalizing on it.
Galio's capacity to go mid lane and win mid-lane fairly decissivly is pretty much -the- reason to pick him.
Oriana,Lux or even someone with High DPS like Syndra or Ahri can outplay him in 1 vs 1 situation .
LoL isn't a game about hard-counters.
Ideally you should be able to win or loose any lane via outplays happening, favoring the more skilled player.
Fighting against Galio as a lot of those champions is pretty cancer though. He can poke for basically the same damage, but he's really durable and has amazing sustain, so you're left with pretty non-existant kill potential against him unless he makes a massive blunder.
The only champions he really counters are someone with long cooldowns AP skills . Like Morgana,Veigar,Brand . Still they can harass him for good 9 levels .
MR and HP items shut down most burst-casters pretty hard, and having respectable health sustain on top of it makes it extremely difficult for any bursty champion to actually kill you.
Spirit Visage alone will turn most melee champions into pretty solid anti-mage champions. Spirit Visage on a champion that already has some pretty impressive health sustain and scales damage with MR is added icing on the cake for Galio.
If you're having issues with any particular mages as the gargoyle, you've made mistakes.
All he needs is ranged Auto . Make him thraw his skin or something . Yes we would need a nerf counterpart .
Throw his skin is a pretty awful visual.
Also, I'd go with the opposite direction for Galio's range.
He's a CC heavy tank made of stone.
Limiting his skillset to close-range would make him more obvious at his intended purpose of being a tank and taunting things, absorbing the AoE bombardment of team-fights and shrugging off damage while he goes in for a 5-man lockdown.
Or just let him cast Gust without stopping his movement.