Molten Core and Blackwing Lair were about as complex as EQ1 raid fights at worst - I mean fuck, a few of them even involved hiding behind a wall to avoid boss AOEs or standing with a back to a wall to mitigate knockbacks and 2nd boss of BWL literally does death touches on tanks every X seconds. If there was complexity, it usually was a gimmick. Like proper use of the orb in the first BWL room
AQ40 is around the time they started to get a bit more complex and Naxx was, IMO, the birth of the "modern" WoW raid.