This is a hard problem.
There are two constitutional guarantees specific to Commons representation; PEI gets 4 seats, as a condition of joining Confederation, and Quebec gets a quarter of the Commons seats, as a condition of the resolution of the great separatism-and-patriation-of-the-constitution debate that consumed 1970 through 1995 in Canadian politics.
Then there's Section 3 of the Charter; it is held to guarantee not only a right to meaningfully participate in the electoral process, but that constituencies should have roughly the same number of voters. This pretty much requires a strict counting rule for seats under proportional representation.
Then there's proportional representation itself; the usual result from proportional representation is a coalition government dependent on a small number of representatives holding extreme views. The extreme views function to drive the agenda. There is no actual fix for this in a pure proportional representation system; it's systemically inevitable.
The other three things about strict proportional representation is that you stop having a riding and a specific MP who represents you, on the one hand, and you are electing from a trivially corruptible ordered party list, on the other. (Exchange of favours for list position in a party list is nigh-impossible to prove. It makes it relatively easy to buy a political party and it makes it incredibly easy to shut out dissident voices.) Those are both bad. The "can't have a by-election" (so resignations for gross moral turpitude, taking bribes, etc. don't cost the party seats immediately) is more annoying than bad.
Oh, and the "while we've got the constitution open..." aspect is a problem; someone is going to try to get a guarantee of private property or similar greed-head thing in there, just to make any meaningful electoral reform impractical. The incumbents never want reform. Nobody now in power wants a system that guarantees they will never again have a majority government.
So, what to do? Getting a majority government with 34% of the exercised vote is obviously not just or democratic. So as citizens we have a compelling reason to change this, but to get it changed we'd need to agree on something to change it into.
Everybody has that Section 3 Charter guarantee of meaningful participation; we can't do anything specific about a proportional representation party list system's trivial corruptibility that involves removing people from it. We can't do anything that works by subscription or produces any additional barrier to exercising the franchise; no setting up representative groups.
Commons is proportional representation. There's a set "divide the votes by 100,000" mechanism with rounding rules and your party gets the resulting number of seats. (The first seat requires the whole 100,000; the second seat comes in at 151,000 or 160,000 or whatever the rounding rules say.) The number of seats in the House is NOT fixed. It depends on the number of votes cast. (That 100,000 is subject to negotiation; think of it as $SEAT-SCALING-CONSTANT.)
ANY member of the party can put their name in the hat for a seat. The leader of the party is guaranteed position one on the party's seating list. "The remaining names are draw randomly by dispassionate officials from Elections Canada" is very tempting but this would be almost impossible to defend; do not give the political parties intense motivation to corrupt Elections Canada. It nearly has to be a party-members-vote; you can vote for everybody on the list of volunteers if you want, or not vote for anybody on the list if you want. The total number of votes received determines seating order. Only when there are ties does something random get used.
There are NO Commons by-elections; is someone dies or resigns, the next person on the party list as of the election that seated this House of Commons gets the seat.
SEAT-SCALING-CONSTANT is different between PEI (to guarantee four seats), Quebec (to guarantee a quarter of the seats), and the rest of Canada. The Quebec-and-PEI values of SEAT-SCALING-CONSTANT for a particular election are only known once all the votes have been cast; none of this Western Canada "we already know who forms the government, why bother voting?" nonsense we have now.
That takes care of the Commons. There isn't an obvious Charter violation in there; it's better than Section 3 with respect to first-past-the-post, since your vote will more certainly elect someone to represent you.
The current Senate's this awful imperial relict thing; it's even worse than the provinces as remnants of 18th century communications technology. So it goes as it is. We need a way to represent dirt; people need a specific representative whose job it is to advocate for them irrespective of party affiliation.
Trouble is, we need a constitutional way to represent dirt. The way I'd prefer is to say that area counts less the more people live there. So about a million people is one senate riding (we don't have the other kind anymore); Toronto and Montreal are a bunch of senate ridings. Senate ridings are either cities (net outflow of taxes, 3 seats) or regions (net inflow of taxes, 2 seats). The Elections Canada folks take this tax flow distinction into account when drawing the riding boundaries and maintaining the riding status; if the net flow of taxes changes per census, so does the senate riding's status.
This won't pass a section 3 challenge; a region has 2 votes with potentially the 40,000 people of Nunavut rather than the 3 votes of the million people in city-riding of Mississauga. Could this be directly added the Constitution? Sure. Would it provoke Section 3 charter challenges? Yes. Can it withstand the Section 3 challenge on Section 1 ("necessary to a free and democratic society") grounds? I think it could; we're giving people who certainly don't have one via the Commons a more meaningful political participation and we're not directly disadvantaging the more populous regions because they've got the Commons. We're doing a checks-and-balances thing but being Canadian we probably ought to call it "many voices".
So we've got 100 senate ridings; Elections Canada draws the boundaries based on combinations of population and area. No more than a million people population per riding; however much area after the cities (that net-outflow of taxes thing being used to set boundaries) are accounted for to make up 100 senate ridings. Provincial and territorial boundaries are explicitly ignored when creating senate ridings.
These 100 ridings elect about 250 Senators via single transferable vote. Senate terms are long (9 years? 15 years?) and staggered; if the terms are 9 years, 1 of a city-riding's senators is up for election every three years. (The first elected senators have to draw lots for who has the initial short term.) Senators very explicitly collectively and jointly represent absolutely everybody in their riding and are institutionally expected to keep no secrets from their fellow-senators in the same riding. They have no party affiliation and may not be members of a political party while holding senatorial office. Senatorial elections are on the fixed rolling schedule; they have nothing to do with Commons elections. (The PM necessarily arises from the Commons.)
A bill can originate in the Commons or the Senate; to become law, it must pass both by simple majority. Neither can override the other.
That's too simple to be an actual detailed proposal and way, way too complicated to sell. This is the big problem with getting rid of first-past-the-post. Any reasonable alternative is complex and it's hard to build a constituency for it. Since it requires opening the constitution, it's got to have a constituency.
16 October 2019
This is a hard problem.