Chief residency certainly doesn't hurt a fellowship application for GI or cards, but someone mentioned above that they think it matters a lot, and I disagree. Most cards PD's don't care that much...it would be somewhat of a feather in your cap but I'd rather be an average resident at a good university program that is well known vs. a chief resident from a weaker university program or a community program.
Mayo Clinic is not a community program.
The Arizona and Florida programs are not as well thought of as the flagship campus, although I certainly wouldn't sneeze at a fellowship done there I wouldn't aim at those places for IM residency (? if they even have IM residencies).
The Step 3 score and the Step 1/2 scores are used by some fellowship programs in cardiology. Other programs did not even want the step scores to be sent, so obviously didn't care about them. If I were a foreign grad, I'd want to maximize everything good in my application, which would include high step scores. I think it would be easier to get a high Step 3 score after a year or two of residency...however, if you must take it earlier, then so be it. If you did well on Step 1/2 and usually do well on standardized tests, then you are unlikely to totally bomb it and probably unlikely it will hurt your fellowship applications a lot.
Needing a visa will be much more damaging to your fellowship application than an average Step 3 score would be, IMHO. Most cards and GI program directors don't want to deal with visas simply because they don't have to...they have a ton of qualified applicants, more than they need,who are already US citizens or permanent residents and don't need visas. Therefore, why should they (or their secretaries, their hospitals, departments, etc.) spend time and money helping coordinate a visa application when it's not necessary to do so. They have to want someone pretty bad, or not be able to find enough qualified people, to be willing to do that. That's why you'd probably find more takers among rheumatology program directors vs. GI, cards or hem/onc.