considering this forum is the first result on a google search of “to run steam you must first connect to the internet” I thought I would post the fix that worked for me - even though it is an old thread.
I am using a Billion BiPac 7404VGOX and I had to change the firewall general policy here:
Configuration
-Firewall
-General Settings
-Policy (changed from Medium security level to Low security level)
Hope it helps someone else.