Which Linux distribution are you using, especially: which DHCP client ?
Maybe Shaw has just misconfigured their DHCP server or their routers in a way that is tolerated by Windows clients, but not by your Linux DHCP client ?
Two ideas that might help in locating the problem:
1) Boot a Knoppix and check if that is DHCPed correctly.
2) Connect your 'problem machine' to a DHCP server to which you have log file access and look at the DHCP server's logfiles. I think ISC's DHCPD will usually log any incoming and outgoing DHCP packets to syslog. At least, it does that on my Debian machines. Maybe that can give you a better idea of what exactly is going wrong.
Edit: One more thing: Since all your network cards are 8139 compatible, changing your problem machine's NIC should not be much effort. I would try that after 1), but before 2).
Maybe Shaw has just misconfigured their DHCP server or their routers in a way that is tolerated by Windows clients, but not by your Linux DHCP client ?
Two ideas that might help in locating the problem:
1) Boot a Knoppix and check if that is DHCPed correctly.
2) Connect your 'problem machine' to a DHCP server to which you have log file access and look at the DHCP server's logfiles. I think ISC's DHCPD will usually log any incoming and outgoing DHCP packets to syslog. At least, it does that on my Debian machines. Maybe that can give you a better idea of what exactly is going wrong.
Edit: One more thing: Since all your network cards are 8139 compatible, changing your problem machine's NIC should not be much effort. I would try that after 1), but before 2).