Tara was definitely on the radar in 1994. She was the US Novice silver medalist and that was the year she surprised everyone and won the Olympic fest over all the older Junior girls, after she was a last-minute addition to the event. That got her the cover of Skating magazine and lots of buzz. I don't know if many had her pegged for the 98 OGM quite yet (more like 2002 probably since she was only 11) but the hype machine was definitely in gear by then. I remember lots of people saying she was going to be something special following Novice nats that year, more so than the actual winner of the competition. That's why the 95 Nationals junior event was supposed to be a coronation for her.
Similarly, in 1998 Sarah Hughes was also on the radar as the 98 Junior national champion with a triple loop/triple loop at age 12. That combo alone got people talking about her as a possible player for 2002.
In 2006 I think many assumed the 2010 OGM would be one of Kim or Asada. As for Shiz, she was at least a known entity who just turned out to be a late bloomer. Of the singles skaters, the only one I might say truly came out of nowhere was Oksana, but that was a different time before the days of Youtube, message boards, etc., so it's hard to say exactly what was going on with her skating back in 92 (I seem to recall she bombed out at Ukrainian nationals?). In this day and age, even the Russian 10 year olds are fairly well known internationally. So I'd wager that the 2018 singles OGMs are skaters we've at least heard of already. Pairs and dance can be a different animal because who knows which partnerships will last, though.