About a year after they were founded, Google was first mentioned in the New York Times. As an aside, in a non-news column.
Today of course, it seems like everything they do is instantly news. It's easy to forget that just about every major online service (eBay, Amazon, Paypal, Twitter, Facebook) launched in obscurity. Same with classic books, pop musicians and political careers.
The big splash might feel good, but it's clearly not necessary.