PhotoJim is right - there is no real answer to such a question. Are we talking about pre-paid or post-paid plans? Where will the phone be used most and what is the coverage like from the various companies in that locale (folks in NL will tell you there is no service outside St John's, so Leaf Fan would be out-of-luck with his fido iPhone should be travel to the Rock or leave the major cities most places outside southern Ontario)? There is generally not a lot to choose between the 3 majors when it comes to pricing but, being a big-city resident in Ontario, I have no idea how Sask Tel, Manitoba Tel or some other regional carriers compare.
In Ontario, what you pay can be a factor of how long you have been with the company and how well you have bargained. As a 10-year or so Telus/Clearnet customer I get a lot of freebies on a family plan that results in it being about 25% less expensive than anything Rogers advertises, but I know Rogers treats its long-term customers well too. I've also had a Rogers pay-as-u-go phone during my contract with Telus (needed a second phone & number temporarily) and can say customer service at both is good to very good, with a slight edge to Telus.
Good luck making the right choice on the Prairies.