Being in the US, I'm not an expert on Canadian cell service, but I believe you use the same 850/1900MHz bands as AT&T in the US, so you should be set for 3G. If you get the Fuze, you'll have to get the unlocked version or get the AT&T model unlocked (not hard at all). The Fuze is a very nice device, but if you get the AT&T version, the firmware and software leave something to be desired-- there's lots of bloatware. Flashing it with an alternative ROM from XDA Developers makes a world of difference-- much better!
The Xperia is a really nice device but it is very, very expensive-- don't know if that's important to you. If you get it, make sure it's the X1a which has north American 3G and not the Euro X1. The camera is the best among the 3, and the GPS is the fastest to get a fix.
The TyTN II is pretty dated and I wouldn't really recommend it over the other 2.