First of all, Rock. I definitely would support it just for it to give a TM and showcase of Stealth Rock, if not that there is Stealth Rock move tutor on the first route. Not sure if giving Stone Miss after the first gym is a good idea. Luck being luck, but not sure if starting with luck based strategies is a good idea.
Grass is okay, I guess. It's a bad type, but something that the player can be prepared for at this point of game with all those birds and bugs on first routes, and it has some interesting options (just don't use Abomasnow, this thing will harm the team, and let's not use Soundproof Abomasnow, because that thing is pointless). Not as much as other types, however.
Psychic is definitely powerful. Without access to Knock Off in early game, I definitely wouldn't put it as a first gym, and Scolipede is weak to Psychic attacks (hi, Gen1 Beedrill).
Fire is Fire. It has many powerful mons, but it also shows the power of Stealth Rock. If Stealth Rock will be available before this gym, then it's definitely an option, but I'm still not sure about starting with it.
Normal is not weak to any of starter types, which makes it great for a first gym. Granted, this type was always problematic in main games, but with competitive background, it might be less of issue. Just make sure there are fighting attacks available.
Poison is weak to Ground and Psychic. Do we have Earthquake available? Do we have psychic attacks available? I doubt so.
I vote for Grass. However, if we would remove Stealth Rock move tutor on first route, Rock is an option too.