Rules for establishing a new Covenant are pretty straightforward. A new Tribunal requires a certain number of Covenants, plus a hefty amount of magi-politics, including recognition at the Grand Tribunal.
Cool.
What does it take to start a new House? Obviously it can be done, because Ex Misc gives us a canon example, but the reactions of the existing houses might range from encouragement to bloody Marching Wizard's War...
So what would be a credible minimum to pull it off -- a certain number of Magi, which other Houses are likely to be in favor or opposed, what sorts of bribes or other leverage would move each of them, etc?
Political consensus that this is a priority topic of consideration for the Grand Tribunal, which meets every 33 years, and otherwise has to deal with very real problems, and has a limited amount of time to deal with those. Chances are, unless you can convince several Praecos and House Primus that such a case is important, it will never be heard. There are also superstitions about having 13 Houses apparently, which may or may not play a role in the politics. Frankly - if you can organise a hundred magi together without becoming Primus of a House, you may have a shot. In practice, most factions stay within Houses or associate accross House lines, and so I would say it would take an event on the magnitude of a risk of civil war in a House that can't be solved, or the Order of Suleiman joining the Order for this to happen.
So, getting the support of (at least one, but more is better) Primi is necessary. Obviously, getting all of the House Primi on-board basically guarantees success -- but that particular task is nigh impossible. Also, part of the challenge is surviving and holding together long enough to make it to (or between several) Grand Tribunals.
More political wrangling, this time to get the rank-and-file magi to support (or at least not oppose) the new House.
Would it take a hundred, though? What are the canon populations of the various Houses? I get that just 'being bigger than the smallest' might not be enough, and being bigger than the biggest might be seen as a threat which works against establishing the new House.
If a large group of 'foreign' magi joined the Order (probably House Ex Misc) en masse, then it would have a large impact. The other Houses might then like the idea of sub-dividing Ex Misc to prevent it from being the largest House. Of course, large groups of foreign mages all joining the Order en masse is exactly how the problems with Diedne supposedly started....
Would it be an easier sell if the new House was a Societas, instead of a True Lineage? Would being a Mystery House make gaining approval more difficult? Would Roman / non-Roman traditions be a factor?
I think it helps if there's a reason they can't just be an ExMisc lineage. IMO, the most likely candidates are the Amazons (who are a Hermetic lineage) and the Soqotrans (geographically distant. Self contained. Have really useful magic that makes vis more plentiful.)
Smallest house is Merinitae at 68 members and the biggest is technically Ex Misc at 180. So in terms of manpower, you're probably looking to bat average with around 100 members.
And in terms of "what kind of house should it be?" I think you'd have the easiest time making another mystery house. The idea would be to catch the order coming and going by offering knowledge some of them covet or need and which the rest would be hated for destroying.
This really is not an easy thing to do though because you'd probably need to produce several breakthroughs to found a practically distinct tradition, and really you're going to want a Hermetic breakthrough for the undeniable clout.
If I was going to do it, I'd get around collecting magi that have been initiated in the non-house mysteries and enlist as many of the Ex Misc who belong to traditions that have been marched in the past. The goal is to get a bunch of people with weird and specialized knowledge, and who all have abiding fear of-- and experience in --being legally called out and victimized by powerful magi. Get them into a like-minded head of steam and fear, then offer them a leg up.
From here, it's a trick of making your group not look a looming threat without looking weak. The best way to do this is by being a serious threat juxtaposed against an even more serious threat. Lucky for you, there is a raiding and killing horde of mongolians kicking around the eastern reaches of Christendom, maybe use that to your advantage. Maybe the Grand Tribunal will make you a house and give you what you want if you'll just let them focus for five seconds on the looming horde of shamans and ranged cavalry.
In sagas I’ve been in, one solution to warfare between the Order of Odin and the Order of Hermes was for the rune magi to join as a new House.
My character argued strongly they should just join Ex Misc, but this was rejected on various grounds:
A) the primus of Ex Misc didn’t want them
B) they would make Ex Misc even larger than they already are (remember that count of 180 is before the current census; Ex Misc could conceivably be much larger than this)
C) It was seen as demeaning. The rune magi wanted to be their own House.
Now some Houses and tribunals didn’t want this. Others did. Integration with the Order eventually happened right near the end of the saga. It was resolved by a vote at Grand Tribunal.
Consider House Miscellanea. Estimated at 180 members, and this is a probably a lowball amount because that's how many magi the House is aware of - and they're not organized enough to keep track of their numbers. None of the Lineage are deemed important enough to warrant their own separate House. Yet, what's the likelihood that we have, say, 30 sahirs spread accross Iberia, the Levant, Provence and north Africa? Why should a smaller lineage get a chance at a House when none of the existing Miscellaneas deserve one? Provence is another case - it's literally a Tribunal caught in a civil war waiting to happen between two Flambeau covenants. 50 might get a shot at a House, but keep in mind - you really are fighting inertia, if you're doing it from the Order. You have to be large enough that the Primus declaring part of your group Orbus is more of a problem than declaring you a House - because deciding on membership and grand Tribunal issues are one of the only power those at the top have (some Houses excepted). It's easier to do it from the outside, arguably, or to get elected Primus by your faction and then conveniently forget you wanted a separate House in the first place.
Political will: A new House will require the sheer force of will to get it done. The Order has added a House only once.
Political mass: There should be a large enough number of magi in the incipient House to make it respectable. This isn't hundreds of years ago, when each Founder had a few followers. You'd need a group of a few dozen, minimum.
Opportunity: House Ex Miscellanea challenged a major enemy of the Order, fought a wide campaign, and then didn't come asking nicely to join -- they started a competing order. This created a crisis. Adding Houses would have to come from some need for Houses.
Allies: A House is not going to be able to just show up. They'll need to have help inside the Order.
Opening: The other Houses should not consider themselves threatened. A menace would have to be crushed. If some other Houses provide a solution to a problem, or avoids a problem, or offers something to the Order in general, they might be acceptable.
Also, one House is not likely to be admitted. 13 Houses would be bad magical hygiene. Several houses might be, perhaps, possibly some cadet group of established Houses, with possibly an Eastern tradition. House Ex Miscellanea might drop two or three major groups.
Possibly in the aftermath of some wide crisis, the Houses might reorganize and re-establish the Order.
Also, the new House would have to be distinct, but socially accessible. They'd have to have Gifted magi, with respectable power, something different from the existing Houses, who can potentially synchronize with Hermetic magic.
If you have all that, the matter can be brought to the Grand Tribunal, presuming there's an ally to bring the matter up. There's probably be several local Tribunals where the subject is discussed.
It's only happened once in the Order's history so I think there are huge obstacles to overcome. First off, if you're talking about an existing House splitting in two I just don't think many magi would actually want to forsake the tradition, culture and philosophy that they've been raised in. I think the issue would go before the Grand Tribunal and they would strike it down if it appeared that the proposed House had little to distinguish it from the one it wanted to split from.
The other possibility is a whole different non-Hermetic tradition wanting to join the Order, but as none of them seem to have the same kind of organisation and leadership that could bring all of the wizards to a consensus decision like that, it's more likely that only a few would want to join and then they would probably end up in House Ex Miscellenea instead. Alternatively, the Grand Tribunal might decide that some other tradition has something to offer the Order and should be invited to join as a new House.
I'd also suggest the settuten, since their Disjunction and regular big gatherings mean they've already got a lot of the organization in place, more so than most folk traditions.
Is it worth also considering what it would take to merge or dissolve houses? Because that occurring at the same time might mitigate the 13 houses problem. Let's say, Mercere falls into irrelevance because of increasing public knowledge of the order, and maybe gets swallowed up by Jerbiton. What does that look like?
As @Aurelius mentioned, there is only one instance of it happening since the founding of the Order of Hermes. So it will be considered the precedent for creating a new House.
Pralix was the first apprentice of Tytalus and was tasked by the Order to solve the threat of Dav'nalleus, one of the few major threats that the Order has faced - Pralix had the prestige that comes with getting that authority.
Pralix persevered and won after the rest of her Hermetic task force were destroyed or fled.
Pralix recruited Gifted wizards from under the rule of the Enemy, turned them into an army larger than any existing House, and defeated the Enemy.
In the process, her army developed bases, supply lines, and other accoutrements of a valid organisation. Also, she was in territory essentially outside the Order's sphere of influence and knowledge.
So according to precedent the elements known to be required to set up a new House:
Be led by someone with Hermetic Prestige and/or worthy of receiving the Order's gratitude.
Lead a large number of Gifted wizards, larger than most existing House populations.
Maintain an effective and sustained organisation with the proven ability to fight (against somebody the Order was afraid of), and independent of existing Hermetic institutions.
Based where it does not infringe the current Order members.
The biggest hurdle is to give a reason why a new house is better than the current situation.
Let us imagine 2 magi. One a great communicator and administrator, who starts organising Ex-Miscellania along Tremere lines. The other magi, a great researcher who is a genius in integrating foreign magic styles.
The researcher successfully integrates multiple other styles in to Hermetic Magi. Lets say Sahir and Rune magic. It can go further. Bonisagus got to 12. It truly does not matter. Ex-Miscellania will now have more than double the membership of any house.
The amazing thing of Bonisagus, is he did not demand fealty. The order are not vassals to house Bonisagus. Because of that starting point, no-one wants a Master House. The last time someone tried to dominate the entire order, the sundering happened.
If Ex-Miscellania ever got organised, due to their numbers, there is a risk of them becoming too influential. That would get magi wanting a solution. Someone offering to drag a lot of magi away from an invigorated House Ex- Miscellania is suddenly very tempting.
Formation of new Houses is one thing, merging or dividing is another. I don't see that the Order has much to say about it, except whether a descendent House's Primus has a seat at the Grand Tribunal. If the Apromar followers of Flambeau split from the House, and declare that their Primus has a seat, does he?
The main thing the Code has to say on Houses (and this is a Tribunal interpretation) is that everyone allows that House Bonisagus may claim/snatch useful/trained apprentices. If the Trianoma* section of House Bonisagus forms a new House, are they descendants of Bonisagus and do they have the same right, or does it only apply to the House that still bears his name?
I could see where a strong tradition might join House Ex Miscellanea, incubate for a while, then divide away.
*It's just a thought experiment. Seems an odd thing for Trianoma followers to do.