I think flexibility should be encouraged, so, leadership "Points" sounds like a good idea. Followers of certain types cost points based on what they are (level x class?). So magic followers are harder to get than say fighters.
Hm, actually, I've got an idea about my earlier " leadership-class-perks" suggestion. If you can make a simple outline I'll get something basic to work with.