There's one other reason I lean "small fleet," and it's this: Starfleet Academy's San Francisco campus is implied and sometimes openly depicted as THE main training center for Starfleet officers. Given that Starfleet doesn't seem to believe in noncoms (though its depiction is not consistent in this regard either) that means they are having to Staff an entire fleet with a graduating class of 2 or 3 thousand cadets every year. That seems like just barely enough to keep their numbers steady, especially for an organization that seems to suffer the kind of random losses Starfleet does in a given year (nearly twice that number of casualties in just the first three seasons of TOS).
Keep in mind that a career of 40 years is apparently equivalent to our 20, and that a number of officers, particularly Vulcans, might have a career of over 100 years. That'll mean higher retention, so 2-3,000 cadets may be enough to meet their needs most years. Add in some years graduating classes early to increase that (up to double, if graduating two whole classes that year), and stop-lossing some of the geezers that were planning to retire, and you can justify a fairly large fleet full of ensign j.g.Picards with a rank of 0-1/2 and 50 years in service.