Re: how the Magi looked
Assuming that we are talking “Magi” as in “Persian Zoroastrian fire priests with excellent astrological/astronomical knowledge and a strong belief in angels,” they would have been pretty darned obvious foreigners in Jerusalem. Same thing if they were Chaldean astrologer/astronomers.
First off, most Zoroastrian Magi lived in Persia. Persia was in a perpetual cold war/hot war cycle with Rome, so it’d be like a bunch of your nation’s archrivals suddenly arriving in Iowa to look for the new Emperor/President/King.
Secondly, Magi fascinated the Greco-Roman world. Everybody knew that they were Wise and Knew Things. They did lots of calendar observations of the celestial bodies. That’s why you sometimes had people like Simon Magus (who was a homeboy from Syria who’d never done anything Zoroastrian) trying to call themselves Magi, the same way somebody today might try to impress someone by saying they’re secretly a Knight Templar or a Navy SEAL.
Thirdly, Persians often wore riding trousers, or riding trousers under robes. In a Greco-Roman world full of people in robes of various kinds, that made you instantly noticeable. The only other people who wore that kind of thing were crazy steppes barbarians, or crazy Northern barbarians. Persians were ultra-civilized, so the contrast freaked out Romans. A lot.