I've been using unlocked and unbranded Nokias on AT&T for years. Just drop the SIM card in the phone and go. They make phones specifically designed for North America that utilize the 3G frequency bands on AT&T as well as Rogers.

The Nokia E71 is a great messaging phone but you may want to wait for the upcoming E72 in a few months. If you want cheaper then perhaps the E63 is an ideal package.