I know this is a bit late, but I hope it helps.
Transgender rights are a bit of a gray area in Canada with the exception of the Northwest Territories (the law there includes the phrase "gender identity" in its anti-discrimination act). It's illegal to discriminate against individuals based on their sexual orientation in all provinces, but nothing explicitly states that a transgendered person cannot have their employment terminated or housing denied. However, you could argue that being fired because you are transitioning violates your freedom from discrimination based on "gender-determined characteristics," which is included in the Human Rights Acts in effect in all Canadian provinces.
My best advice would be to be you, and fight any misguided wrongdoing that comes your way. If someone DOES try to deny you employment or fire you based solely on your status as a transgendered person, contact your provincial human rights commission. You can also write the Court Challenges Program and ask that gender identification be clearly stated in the law.
And...like Andrew said, some people will fire you and cite another issue (downsizing, you were late by four minutes that one time, your handwriting is poor, etc.) when they really don't want you working there for reasons that legally cannot fire you for. I've had this happen to me regarding issues that weren't gender related. I'm not sure what can be done about that, as legally they've fired you for acceptable reasons. When that happened to me I just wrote off those jerks and found a job that didn't have an issue with who I am.