It was my impression that Gmail's big hit was its use of AJAX more than just its use of Javascript in general. Until then, it was just this obscure thing MS created, but it wasn't really used in the wild until Gmail.
It was used, but mostly for internal applications or websites that were willing to dictate a minimum browser. Firefox was only released in 2002. By 2004, it had hit a critical enough mass that it was reasonable to tell a user they needed as good as IE or Firefox at the time (for a beta project).