Beyond Good & Evil has a girl, albeit that's not classic in terms of consoles it's on yet.

Pokemon Crystal allowed you to play as a girl character. Castlevania Legends involves a Sonya Belmont as the lead character, and it is arguable that Lizzie from Rampage is supposed to be a girl :P

Oh yes, and Space Channel 5 had a female lead! And Zillion for the SMS has one of the three main heroes a girl.