For me, it really comes down to being at a gym where the philosophy matches my dd's personality and long term goals. The size of the gym does play into it, but I wouldn't put all your stock in that. There are many things to think about. Some gyms emphasize skills and some fundamentals and conditioning. Some gyms are great at compulsory levels and win everything and then have nothing to show for at the higher optional levels. Some gyms have an eastern european coach and philosophy and some have a more American feel (this is something that most people wouldn't think about, but is a big difference) and some kids will respond better to one or the other.
I think one thing you will find around here is that the vast majority of people have something to say about the communication at their gym. Unfortunately, there are a rare and lucky few that are at gyms where communication is clear and regular.
I would focus on it feeling right and fitting your daughters goals. Does she want to win over the next couple of years and then move onto other things in school and sports or are high level gymnastics and college scholarships the goal or something in between? I know it is impossible to know any of that for sure right now, but you may have a feeling one way or the other. Talking to lots of parents, it seems that most do.
Losing a head coach is a big ordeal. Is this the head coach of the whole program or the compulsory head coach. If the top coach at the gym left abruptly, that would worry me more. Also, it might be possible that it looks abrupt to you, but that the leave had been being discussed on the back end for a while. We had a coach leave that was all the girls favorites and it was really hard for many of them who had been with him for a long time. We got 3 days notice, but he said that he told the gym he was leaving months prior. My dd was a wreck after this coach left, but it turned out the new coach that replaced him was a much better coaching fit for her and although she was scared, they hit it off and she made a lot of progress really quick with the new coach. Just some food for thought
Trust your gut and daughter and you guys will figure out what is best for you. Good luck and Welcome!