Since seacláid is feminine, shouldn't we "an tseacláid" or maybe "an sheacláid?"
Yes, it should be an tseacláid since it’s feminine; not genitive; and begins with an S followed by a vowel.