I suppose it depends what you mean by large and effective.

Administration was not evenly distributed in all places and 'effective' administration of one province at a particular time didn't mean that other provinces would see the same. Early Arab-ruled Egypt seems to have been remarkably well-administered. There's (relatively) extensive papyrological source material from Egypt for this period, such as the archives of the pagarch Flavius Papas, that seems to indicate a strong continuity in effective and stable administration. Compare that with, say, Arabia itself, where we have next to nothing suggesting an elaborate bureaucracy in the 7th century. It's possible the evidence just hasn't survived, but nothing points to an elaborate bureaucracy in Syria or Palestine in the early years of Arab rule either. The general impression among historians is that the Arabs co-opted existing bureaucracy in Egypt left over from the Romans (as they did for things like the old Sassanian postal service in Iraq) suggesting that some specific regions did indeed have somewhat effective civil services by this point that were at least good enough to keep around. However, the flip side is that we don't see it for the entire caliphate/state until much later. Basically, you get some regions within states that might have a strong bureaucracy and other parts that don't.

Tang China (AD 618-907) might be the definitive example of the first truly large bureaucracy. They're the ones that implemented China's famous examination system to create an educated class of Confucian civil servants. These scholar-officials would be the ones consulting with the emperor on policy, managing the prefectures, and overseeing the all-important tax functions.

So you can date large bureaucracies to at least the 7th century, if not earlier. Effective, on the other hand? That's hard to say. Remember that, for the majority of history, the primary function of a state bureaucracy was the management and collection of taxes. It's pretty hard to say exactly how much of the actual tax collected ended up in central hands. Some of the estimates I've seen for Roman-held Egypt on the eve of the Arab conquests have been as low as 5% getting back to the imperial centre. What qualifies as 'effective' then ends up being pretty subjective. Is effectiveness measured purely by returning tax revenue to the centre? Is it determined by fair administration that doesn't provoke rebellion? That's a judgement that historians don't all agree on.

Bureaucracies also reflect the needs of the day. The civil service of a modern Western nation like the USA is massive because the role of the state is massive. Back when the government did little more than tax you every now and again and occasionally raise armies, you really don't need big bureaucracies in order to function. In that case, 'large' and 'small' are relative. 100 civil servants isn't small if 100 servants can cover literally every necessary function of your particular polity.

Basically, I'd lean towards saying the Tang fit your description best. However, like many things in history, it's a slippery thing to nail down and define in exact terms what a 'large and effective civil service' even is for different periods and places.