https://fred.stlouisfed.org/graph/?g=YUZM
Sure, it was still above 5% in 96 nationally. But strongly down from the summer of 92 peak.
Additionally, Netscape's IPO was in August 1995. I wouldn't call that a bad environment for starting an internet company.
People building Internet infrastructure (Cisco, Sun, etc.) were making some decent money, but actual Internet businesses? Not really.
In fact even by 98, 99, '00, Google itself had no real viable business model. Despite becoming a household name already.
> Google was born into an economy that was just starting to recover from being bad.
I don't think being grad students at Stanford and then incorporating in 1998 counts as "just starting to recover". The economy in 1996 wasn't bad. 1998 definitely wasn't.