I have a similar problem, and I think I ruled out the low-tech solution. First, the set-up. I have a 2 gig dual G5 connected by modem to the internet (yes, I live in a rural area). The connection works fine. I had a G4 powerbook hooked to the G5 with a crossover ethernet cable to share a printer. By accident, I found I was sharing the internet connection.
Later, I used the same crossover cable with my G4 Cube and set it up to share the connection. I set up the G5 to share a dial-up connection via ethernet. When I tried to use Safari, I got waits of about 30 seconds before I got the message the server could not be located. If I was not connected at all, Safari would instantly tell me I had no connection. I tried turning the firewalls on and off. I was able to log into each computer from the other via file sharing. Network sharing had a green light for the ethernet connection. But the Cube's browser couldn't access the net.
I then tried the same thing with the powerbook. Same results. I then tried a shorter straight ethernet cable (os x is supposed to be able to recognize the kind of cable, and it seemed to). Same results.
I tried using Internet Explorer, instead of Safari. Same results.
The G5 runs 10.3.5; the Cube 10.3; and the powerbook 10.3.5.
If it hadn't worked by accident when I wasn't even trying to set it up, I might be frustrated but I wouldn't be this disgusted. Anyone have any ideas?