is there any objective reason for this, or is it a "we're marines, we do things by 3's" and "we're army, we do things by 2's" thing?
There are differences of opinion about how many things one leader can keep track of, and about what size unit is most flexible. Generally, though, you're going to have each leader responsible for somewhere between 3 to 5 subordinate units. One of the usual tactics will probably be to have one element pin the enemy with fire while another element advances; if more elements are present, you can either keep a reserve, reinforce another element, or envelop your opponent. James Webb wrote an interesting article in 1972 on
reorganizing USMC fire teams, though it doesn't seem to have ever gotten serious consideration. The problem with splitting a squad into many smaller units is that the smaller units can become ineffective or even totally disappear if they take casualties, and there's no consensus on just what the optimum mix is for balancing flexibility and resistance to damage.
Your weapons mix will also affect your TO&E (Table of Organization & Equipment) -- if you can only afford two "heavy weapons" per squad, it makes little sense to split into three elements. There's also the problem of transportation; it's a bad idea to have a squad so large that it needs 1.5 APCs to carry it, for example. If your available vehicles put restrictions on you, that may solve your problem; if you can customize your vehicles to your ideal squad, you're a lucky commander indeed.
It's also not always easy to ignore the influences of tradition, whatever the tradition is that they're coming from. It's possible that a certain organizational structure may be adopted because that was the structure that the CO trained with, and he's not comfortable with (or willing to) adopt anything else.
I would expect a lower-tech mercenary company like the one you're describing to be a specialist in some particular field, whether it's protected-forces operations, city fighting, special ops, reconnaissance, or something else like that. Their organization will probably be determined by their specialty and the gear and tactics required for that job.
If you did run across a unit that was strictly line infantry... I'd expect them to be mechanized infantry, and so the carrying capacity of their vehicles would be a major factor. One squad per APC, with additional vehicles for HQ troops, would be my guideline. If you are customizing the APCs, come up with a number that makes you happy and meets any transport requirements; I like a capacity of 16, which allows for a driver, gunner, squad leader, 3 4-man fire teams, and a casualty/prisoner/observer. It's also pretty damn huge for an APC, which is a disadvantage; as an example, a Stryker only carries a 9-man squad plus two vehicle crewmen. Instead, you're looking at something more like the size of a USMC AAV, which carries 25 combat-loaded Marines. Sure, advanced technology will enable you to cut the size somewhat, but it's still hard to cram that many guys into a tiny hull.
There may be limits on the maximum size of an APC, depending on your requirements -- does it have to be amphibious? Does it have to fit in a C-130? Does it have to be airdroppable? What sort of firepower should it provide? Your vehicle design rules will help you define the possibilities, and without some idea of what you're using, I can't speak to what's going to be optimal.