In Australia I was doing basic surgical training...would have gone on to do ortho. In the US I am doing anesthesiology. I chose to do anesthesia over surgery mainly for lifestyle issue. Also, I did 3 months of anesthesia in Australia before leaving and I really enjoyed it.
It wasn't very difficult to get into a residency here, but then again I had really good USMLE scores. The main difficulty for me was that the whole process was very expensive (applying, traveling, accomodation, etc).
It really depends on what you want to do. If you want internal med, peds, psych, or path I think it's pretty easy. Anesthesia and surgery are becoming very competitive (ie. upwards of 100 applicates for every one spot in some places). Derm, Optho, and Rads are very, very difficult for a non-US to secure.
The most important thing for a non-US student to get recognized though is USMLE scores. You must do well.