I have shipped to canada a couple times. Nothing really hard. IIRC, there is a small little customs form you have to fill out stating whats in it and whatnot, then its on its way.
Though I do not know for sure, but if I had to guess, I would bet the post office would be more reasonable on shipping than fedex. Both times I have shipped up there it was through the post office. I think I have even shipped something to france before.