I got my first protectorate when playing as the Suleucids. Having driven Thrace out of Greece I offered them protectorate status. They refused so I took yet another city and offered again, this time adding “Accept or we will attack.” They replied with something along the lines of “We don’t seem to have much choice so we accept. But we’re not thanking any of the gods for this situation!”

They went on to pay regular tribute that gradually went up and down between as much as 12,000 and as little as 200 per turn. I think they had three or four regions left so they were still viable. In fact my Thracian thralls continued to field several large armies.