Well, TOS made this a little easier in establishing that most the member worlds of the Federation still maintained their own fleets.
Where? How?
The captains and first officers of the big ships seem to know each other.
Do they? We have rather little evidence of even this.
* Picard knew fellow
Galaxy class skipper Varley, but there's no indication anybody else in Picard's crew knew him or any of
his crew. It would only make sense that the skippers of these leading Starfleet vessels would know each other by reputation at least - and that was as far as the Picard/Varley thing ever got.
* Picard also knew the skipper of the ship that had "donated" Riker to him. But again apparently only by reputation - and for the obvious reason that he had had previous dealings with DeSoto.
* Sisko knew Picard by reputation. Everybody in Starfleet would.
* Riker met his former captain Pressman once. This was by deliberate design, not by chance meeting - Pressman sought him out.
So far, then, we have zero cases of officers "unduly" knowing each other. Let's see if we can scrape together some:
* Riker met his former classmate Rice in "Arsenal of Freedom" by chance. Or then his ship was sent out exactly because he knew Rice...
* Dax and Keogh, with previous bad blood between them, met by chance in "Jem'Hadar". However, Dax apparently was know to Keogh through its civilian Curzon persona, as Keogh e.g. asked if Dax had ever considered serving on a starship and got a satisfactory "no" for answer. The skipper of a diplomatic gunboat would have every right to know the famed ambassador-at-large.
* Sisko and his good, close friend Hudson met at the DMZ by chance in "The Maquis". I can think of no excuse here.
* Sisko met Sanders in "For the Uniform" and Reynolds in "A Time to Stand", but there's no indication that they were close friends, and it would be justified to have Sisko eventually learn to know skippers who operate in his area.
It's not really a small Starfleet in TNG, then, and obviously not in VOY where only one fellow skipper is met and is said to be known only by reputation. It's not necessarily a small Starfleet in TOS, either, as none of the fellow
Constitution skippers Kirk meets by chance are said to be close friends despite this being perfectly allowable for "stablemates". Sure, Kirk is on a first-name basis with them all - but he's that with basically anyone he meets "on his level". He has also gathered at least two close friends of his, Mitchell and McCoy, to serve with him, but that's not an issue left to chance.
Basically, then, we only get these chance encounters once in TNG and twice or thrice in DS9, which IMHO doesn't yet prove that Starfleet would be a one-horse town.
In TNG a fleet of forty vessels is considered a significant concentration of force, loss of which is a serious blow. That really do not sit too well with an idea of a military with 8000 ships in it's disposal.
That is easily excusable by saying that it takes years to assemble those thousands of ships into a fighting force. We see as much in DS9, where Starfleet desperately stalls before launching its attack against the Dominion.
I don't see a paradigm shift, either. The writers of TNG knew that the VFX people could never show even forty ships simultaneously on the screen, let alone a hundred. So they wrote in all sorts of excuses for showing fewer ships, while at the same time making it clear that these were just excuses. When there are two dozen ships in "Redemption" (portrayed by just four on screen!), the villains express amazement that Starfleet would try and invade with such a minuscule force. When there are forty in "Best of Both Worlds", that's again the best they could assemble in a short time. When Starfleet sends reinforcements of six to nine ships to DS9 (portrayed at best by four ships again), it's because the station is so distant, a lone beacon in the night and all that.
And when the VFX evolves, the writers still keep at it. Forty Klingon ships are shown attacking DS9 in "Way of the Warrior", yet they are said to be part of a force where "even the first wave" featured 150 ships. OTOH, the writers still overcompensate: the VFX shows the station spitting out enough fire to discomfort dozens of enemy ships, but Kira only mentions something like eight hits...
Generally speaking, Starfleet has always been a force that can in theory challenge the known universe, but in practice never manages to send more than one ship to respond to the crisis of the week. A three-digit number of ships is a good compromise for that, IMHO.
Timo Saloniemi