Innanzitutto, se è possibile è meglio esportare con Xfig in formato picture (così è “includibile” da parte di qualsiasi compilatore).
Secondariamente, per quanto riguarda immagini bitmap con compilatore pdflatex: se non si hanno problemi di spazio (e direi che non è mai questo caso, visto che dovendo magari essere trasportati sulla rete qualche Megabyte in meno fa comodo) la situazione migliore è uno scaling diretto in LaTeX: nessuna informazione persa e viene fatta una sola modifica.
IMHO, non si cade mai nel primo caso: secondo me, è sempre necessario ridimensionare le immagini perché abbiano larghezza pari a \textwidth. E’ difficile che si voglia fare più grande e nel contempo, ridimensionando l’immagine, si risparmiano qualche mega.
In merito al ridimensionamento, quanto si può fare per evitare di creare artefatti è tutto buono (ma non sono un grafico e quindi non saprei darti informazioni più precise).
Ciao.