The Raiders, Steelers, and Packers all have a significant national following, maybe in that order. And the Steelheads may be a little more visible right now just due to recent success. But I don't think any of those teams have quite the national fanbase that "America's Team" (wow, do I hate that) has.
(I travel a lot too, and I've lived all over the country.)