Since the Parthians ruled Persia at the time of Christ’s birth, examples of Parthian dress might give you some ideas. This site includes some pictures (can’t find any of priests, however): http://www.parthia.com/parthia_arts.htm
As for depictions of the magi in Christian art, check out paintings by Gentile da Fabriano, Hieronymus Bosch (better detail here), Botticelli, Ghirlandaio, Gozzoli, Massys, Rogier van der Weyden … quite a variety of costume, although, as JR Brown points out, the artists typically just put Caspar and Balthasar in whatever passed as exotic, “Eastern” dress by medieval and Renaissance European standards.
It’s also interesting to point out that in many of the paintings, each magus is associated with a different age of man–Balthasar representing “Youth,” Caspar “Maturity,” and Melchior “Old Age.” Some artists would also associate each figure with a different region of the world, and give that figure what were considered the typical racial features for the respective region (Balthasar = Africa, Caspar = Asia, Melchior = Europe). Not all artists did this, though–I think it was more common in Northern Europe. capybara could explain it better than I can (and will hopefully be along soon with some additional examples).
Edited to add: if you haven’t selected a magus yet, Balthasar would give you more opportunities to vamp it up, at least if you’re going according to his depiction in Renaissance art–since he’s usually the youngest magus, he tends to dress the most flamboyantly. Just something to consider.