I think something like the below could be interesting, and fit both our desires.

Act 1:
You meet 5-7 potential followers, from whom 3 stay with you later in the game. The others either dies, or wander off based on your choices you make through act 1.
(Party of 4)

Act 2:
You start with the 3 you finished act 1, and meet a further 3-4 potential characters that could join you.
Based on your previous deeds, some might not want to join up with you, and some meet their faith through act 2.
At the end of act 2 you end up with 4 followers in your party. (Party of 5)

Act 3:
You start with the 4 from act 2, and meet another 2-3 potential allies.
And you get (the option to have) 5 followers now. (party of 6)

I think that way it would actually add to replay value of the game, you still have to make decisions, and the idea of slowly growing your party is also nice one.

This way maybe everyone gets what they desire.