Perhaps it could be a vassal interaction similar to Scutage? If a vassal is big enough you can choose to get an extra diplomat instead of extra tax when you relieve them of war duty.
This would work, however, it would also be a DLC-only thing - since vassal interaction is a feature of Common Sense. I personally wouldn't mind that, it might not go over too well with some people here, I'm afraid.
Perhaps, something along the lines of:
vassal/PU has (exact numbers of course subject to balancing):
- more than, say, 5 provinces (or more than x development)
- less than 25 liberty desire
- more than 125 opinion of its overlord
As an additional idea, and a way to compensate for the loss of the unique buildings that grant leader upkeep, what about marches above a certain (not trivial to achieve) level of army and/or navy tradition granting an additional leader? (the historical "justification" being that the overlord can draw from a subject's officer pool). That way, all types of subjects (except protectorates) might provide their overlord a special boon and become more diverse in their utility.