Question: what is the best choice for the shape of a gaussian surface?
Answer: For point charge or homogeneously charged sphere you can predict from the symmetry of charge distribution that field would be directed along the corresponding radius. Thus a choice of a sphere as a Gauss surface is natural. For infinite string the surface is a cylinder, because you have cylindrical symmetry, etc.