As a complement to the other answers.
As it stands, the question is about the 19th century autonomy of future independent states, although it mentions other cases (Tunis, Wallachia, Moldavia, which had traditionally been semi-independent). At the same time it may seem contradictory ("Why did the great powers not simply annex these territories, and why were the tributary states not just declared independent?") were it not for the fact that the condition under which those states existed was itself contradictory or paradoxical.
To answer those questions:
"Why did the great powers not simply annex these territories?" - Those territories were partially occupied by the great powers that were present on the ground - like Austria (see below) and Russia (Eastern Moldavia, which was after that called Bessarabia - today the Republic of Moldova).
There's the rub: at some point the decisive powers that could intervene on the ground (Crimean War) were coming from too far away. This situation has resolved the problem "occupation versus independence" in favor of the latter:
Why were the tributary states not just declared independent? - They were declared in the end.
The European powers interested in and capable of intervening in the Russian - Ottoman dispute over the Balkans were Britain, France, but also Austria. In the absence of these actors it is most probable that the region would have passed from the Turks to the Russians.
In the 17th and 18th centuries, before the British and the French had the power and the interest in intervening in that region, Austria was the only power that - beside Russia - could (and did) take over that territory from the Ottomans (Hungary beginning with 1570, and Transylvania - after 1686, both fully by 1711; Vojvodina - 1699, Banat - 1716, Oltenia (Western Wallachia) - 1718-1737, Bukovina - 1774; Bosnia - 1878).
Excepting the Romanian principalities of Wallachia and Moldavia the semi-independence of the Balkan states is a 19th century matter, coinciding with the declining power of the Habsburg in favor of Germany and the Western powers, England and France, and with the mounting adversity between Germany and Austria, on the one hand, and France and England on the other.
The new factor that intervened in this way is that England and France had no territorial vicinity to the region, and still they played the decisive role in keeping Russia out of the Balkans in the 19th century, culminating in the Crimean War. As these territories could only indirectly be controlled by them, a process was started during which they went slowly towards independence.
That full independence was not granted directly is not at all surprising. States cannot be created overnight. (North of the Danube, Transylvania, Moldavia and Wallachia were dominated by the Ottomans but kept their statehood; by contrast, south of the Danube there was no Serbian, Bulgarian or Greek statehood left.) At the same time, the interests of the greater actors that were affected by the new states needed to be considered first.
What should be considered surprising is maybe, on the contrary, the very existence of the new states - not that they were just semi-independent, but that their independence was granted by the great powers. For the new states to become independent a certain "power-void" needed to exist, but at the same time the presence of a special force was needed which could ensure their protection against their stronger neighbors - and that was precisely the kind of role that France and England were ready to exercise at a certain point.
That paradoxical role of far yet efficient protection was played for certain newly-independent states by different actors. It was England and France for the Danubian Principalities and then Romania at a certain point when Russia and Austria were too close and too powerful to play that role; but then, when the independence of the country was confirmed (so that Austria was no longer a menace, while France seemed weaker after 1871), Romania secretly joined the Triple Alliance of Germany, Austria-Hungary and Italy; Bulgaria went towards Germany, Serbia towards Russia.
When this logic was destroyed by the triumph of one of the powerful neighbors (Germany+Austria-Hungary between the Russian Revolution and the end of WW1; Germany during the first part of WW2, Russia after WW2), the independence of these states was severely affected.
One can see even today this "far yet efficient" kind of power - it was and still is largely represented by the United States; Russia played also this role in the past - notably in Cuba - and recently in Syria.