We've done Gymboree (18 mos.), Little Gym (age 2-3) and a competitive gym (age 3-4). I have to say that Little Gym was my absolute favorite. We started out in the parent/child class when DD was 2, but she kept ditching me and doing stuff on her own so they bumped her up to a solo class (I think they were called Funny Bugs). We don't have a My Gym in the area so I can't comment on a comparison there, but what I really liked about Little Gym is that the kids actually use scaled-down versions of real gym equipment. Gymboree didn't use these, and the gym where she is now puts the kids on the bigger equipment. I think that getting up on a balance beam and flipping around on parallel bars helped alleviate any future apprehensions about gym equipment. The teachers also made the classes fun, parents were more than welcome to watch the classes, and they did these cute little gym routines at the end of the semester and got medals. I actually like TLG better than the competitive program DD is in now, but I had scheduling conflicts with TLG. Ours is fairly new so there aren't as many classes per level.
ETA: Cost-wise, they are all about the same here, about $200/semester. I know Gymboree and TLG have trial classes and open enrollment throughout. I would just take your DD to trial classes at all of them and see which you like the best.