Using connect to server will recognise the PC in Windows/Samba networking, which is its own little subset of the whole networking picture. Don't get hung up on this, all it means is the Mac is establishing the Windows network, which is why if the mac is started first the PC will appear.
What you do need to focus on is the broader picture of IP networking, and that means PINGing the machines to ensure that they're talking to each other. In windows, there is a command "ping" which can be entered at the DOS prompt and works much the same as the Unix command. On the Mac, you can use the ping command from the command line, or use ping from the Network Utility.
If you are going to use the mac as an internet sharing gateway, you'll need to tell the PC where to find the mac. I would have thought the PC could access the network via the modem, but lets be honest: these things are just wierd.
I'm hoping someone with a little more experience with hubs and broadband modems can help us out on this one!