The Roman Empire was already acquainted with Steppe peoples, Persians, North Africans, &c. Can you give us a timeline to work with? We could go into the Huns and the Avars terrorizing Eastern Europe, their reputation as fearsome riders (the Avars introduced the iron stirrup to Europe!) but I get the sense that's not what you're looking for.

Different races occasionally pop up in hagiographies, usually in some attempt to denote "evil" and "good" by how black or "milky" the skin was, but that's probably the most racist thing you'll find.