You really don't have much choice given the BC interior and Vancouver Island are important. It's Telus Mobility and look for a North American LD add-on package.
If you were going to be in Vancouver and Victoria most of the time, Rogers and Bell would be options, but coverage will will not be as good "away".
Telus offers both CDMA and HSPA (GSM) handsets. The HSPA network is new and you need to verify its available where you will be in the interior. There are still some gaps and service issues as it's less than3 months old. If you choose HSPA, Telus and Bell share the same network so then it's a matter of who has the best prices and plan. All three will offer you discounts if you combine cableTV, internet and wireless.
You will also hear about new providers like Wind and Mobilicity but their services are limited to the cities and you will be doing a lot of roaming on Roger's network - see about about less coverage in the interior. Probably not what you want.