> Without having already done the classes you did, it would be very difficult to motivate category theory and it's liable to just make students' eyes glaze over.

There's enough motivation for category theory even in basic foundations. You could start by teaching a structural set theory like ETCS as the formal counterpart of naïve set theory. Then yes, teach abstract algebra as usual but introduce category-theoretical generalizations early instead of duplicating content.