On my last Roman game, I never found the expense of client rulers to be a big deal at all. And I had a lot of them. Literally every new province would get one, and I'd progress through the government types at 30-year intervals.