I am Canadian citizen working in the US (from Toronto). Moved here back in 06. I can tell you that to be working for a US company, whether it's remote or physical, you'll need an SSN and a TN Visa. In order to get your SSN, you'll need a TN Visa first. You'll get your W-2 from the US and will have to file your taxes here in the US. Technically, you'll be treated as a US employee that's remotely located in Canada.
I don't believe there's legal issues since a TN visa is something you can get by crossing the border with an 'offer letter' from the company. There aren't any legal fees that your company have to pay. Possibly expenses for the visa ($200ish?) and perhaps some travel.
EDIT: You'll have to physically come to the US in the beginning to get your SSN and TN Visa. Every 2 years when you renew, you can just cross the border and then come back but use that time to see some cities (if financially possible).