I think a party size of 5 would be good. 6 would be better but it would require a lot of work to rebalance the whole game.
But 4 is definitely too small and won't allow much creativity. In a game with so many classes and subclasses, this number drasticaly reduce our possibilities and a lot of players will be frustrated not to have a bonus slots or two to try less "classic" classes.