At the time he left MSU, he had 6 total years of head coaching experience (5 at MSU, 1 at Toledo). It was far from obvious at that point that he would be an all-time great. Keep in mind that at MSU he was dealing with scholarship reductions leftover from Perles until his final season.
Of course, within 2 years he won the SEC at LSU, and in 4 years won the National Championship. I recall his name being mentioned in the 2nd tier of candidates during the post-Davie searches. While he would have been preferential to Ty at the time, I think that based on existing evidence in December of 2001, O'Leary would have been considered the more solid hire. I have also heard rumors that Monk nixed a potential Saban hire in favor of Ty during the 2nd search in December of 2001.
Either way, by the time Alabama hired him, he had 11 years of D-1A head coaching experience, 10 years of major conference experience, and an additional 2 years of NFL head coaching experience. A more experienced, more seasoned, and likely more skilled coach than the one who left East Lansing for Baton Rouge in 1999.