Udyr, Garen, and Blitzcrank (and anyone with on-hit hard CC) can stop Galio from ulting. He is generally just beaten by bruisers with mean damage.

Udyr can cancel his ult with bear stance

Nega-Galio
It's actually not a champion, but a hole in the space-time continuum shaped like Galio.
But it's still a counter.

Xin Zhao, three talon would interrupt.

I can see Talon working out decently enough.

true damage are something to watch out for - olaf/cho/ahri

on hit stun/silence (as it cancels your ult which blows) - udyr/irelia (also true damage too)/leona/garen/voli

anyone with a disable

Almost any bruiser will be able to free farm with galio not being able to do a **** thing about it... (renekton, jax, nasus etc). Mid lane is definitely where galio shines~can hold his own vs many aps, especially if abby scept is rushed-- a good Morgana or Ryze are probably the biggest pain in the ass for me though, especially with jungle pressure.