As stated above, seeing the property is vital and finding a contractor will take some research, as you may very well get quotes based on their work load. Sometimes contractors will bid high, as they may be too busy to take on more and this could be their justification for the addition. I'm not in the Edmonton market, so I don't have any contractor referrals, but here is a start as you've requested.
"Also the gas heat is controlled by the upstairs and how would I go about separating that? Do I just put in electric baseboards?"
If you put in extra electric baseboard heaters, you'll probably be opening walls to run the wiring, unless you have T-Bar in the basement as a ceiling, but still may have to open outside walls. Not sure if Edmonton allows T-Bar in the basement upon legalizing a suite, but I'm guessing not, so you could be opening walls anyway.
Also, you'll have to ensure your main panel have the capacity to handle the extra load. If it can and there's no space left in the panel, then you add a 2nd panel, called a sub-panel and put the extra breakers in that. Not knowing the electric load your property is drawing, I'm going to guess you have a 100 amp panel and adding a 60 amp sub-panel is common, but have it checked by a certified electrician. Just add the amount of heaters, total Wattage and divide by 240 volts to get the current draw. My guess is it will be below 45 amps, which makes a 60 amp sub-panel work. I'm also assuming you'll be adding multiple thermostats on the wall, rather than the relying on the heaters dial, as that's not all that attractive to tenants. They'll likely not turn it down if they go away for a while.
Of course the quick fix for now, is to add another thermostat in the basement and parallel the thermostats upstairs and downstairs, so the thermostat that is turned up the highest wins. Not ideal, but a quick fix and you'll have to let both tenants know that is the case. On one of my properties, I added the 2nd thermostat in the basement and installed a switch in the basement to toggle between up and down, as my basement tenant didn't like it to warm. This idea came to light, simply because the upstairs tenant went on vacation and left the thermostat too high. Also, not ideal, but its been working fine this way for years now and I do remind them all the time to remember the thermostat if you go away. Of course, this particular property is in close proximity to where I reside, which may not be ideal for you in Vancouver, but matching up and down tenants as best you can upon screening, should help as a mitigation.