I think the system is different in Canada - the PM is the leader of the party with the most members in parliament. So, you could have an atheist as PM without too much fuss being made of it (at least, I hope so).
It would interesting to see what would happen in the US, if you had a Muslim being the candidate for one party and an atheist as the candidate for the other party...probably not in my lifetime
