Arbok, Steelix, Seviper, Eelektross, etc - know that's a really simplified example, but so much could be done with that kind-of thinking and it would really open up the challenges a bit more. I think someone earlier in the thread suggested a Trick Room based Gym, which would be really cool and different.
Like, the tree-swinging gym could be adapted to use Pokémon like Primeape, Sudowoodo, Ambipom, the elemental monkeys, to give a bit more diversity... which just gave me thought, given how they seem to pushing the 3D environment a bit with this game, maybe the Gyms each specialise in one kind of environment and use Pokémon that live in said environment?
For a long time, I've liked the idea of seeing dual/multi-type gyms. Like a gym down a cave or up a mountain where it's Ice/Rock type, an industrial city by the coast where there's a Water/Electric type gym, a Fire/Ground type gym out in the desert or a Fighting/Steel type "warrior" themed gym. Those may not be the most challenging combinations in battle but you get the idea. I also think it'd be neat to have a gym of two levels; one level with one gym leader's theme and you go up a floor to a slightly different theme and battle the second gym leader to get the badge.
(Feel free to message me, if you'd like to trade; I'm just not able to always guarantee my availability).
I'd would die if they had a Ghost Type Gym Leader who was a Gothic Lolita!
I'm at the very least hoping each Gym Leader has more than three Pokemon. Give them a full six, please. Pokemon can repeat, that's fine with me, but it's gotten to the point where they're not even challenging and don't serve the title of "boss battle" justice. They're no better than any other trainer and frankly are just a pleasant change in background music.
Aside from that, I hope the Gym Leaders are all given plot-heavy backgrounds. Really involve them into the story. Maybe make one Gym Leader the player character's brother or sister, or let's see Norman v2.0. I was much more pleased with characters like Clay and Marlon, who had accents and used slang and epitomized their stereotypes. They seemed extremely human and were definitely relatable. As long as GameFreak improves upon the characters we had in Black & White then we should be in good shape.
I hope the gym leaders are a bit more challenging this time around. I found most of the Unova gym leaders minus Lenora very easy to beat. I also think the later Gym leaders should have more Pokemon or a full team, I actually want a challenge when I fight a Gym leader.
I don't like the idea of the first leaders having a team of six Pokémon. It should be like this:
1st leader: Two Pokémon
2nd leader: Three Pokémon
3rd leader: Three Pokémon
4th leader: Four Pokémon
5th leader: Four Pokémon
6th leader: Five Pokémon
7th leader: Five Pokémon
8th leader: Six Pokémon
Anyway, it seems we will get one more Bug-type Gym and I really hope we finally get a female Bug-type Gym Leader this time.