It sounds like you're having DNS issues. Most Cocoa apps make DNS calls that are handled via mDNSResponder nowadays, so if the mDNSResponder process is having a problem, even traditional unicast DNS lookups will fail. Next time this happens, try...
sudo killall -9 mDNSResponder
...this is sure to kill mDNSResponder. Don't worry, launchd will automatically restart it.
It's possible that whatever was causing mDNSResponder to hang was cleared up by your troubleshooting steps, or maybe you triggered a network configuration change that cause mDNSResponder to reload itself.
There are still a few command-line tools that use traditional Unix DNS resolver libraries that don't leverage mDNSResponder. These include host, dig, and nslookup. Another way to see if it's just mDNSResponder and not DNS in general is to use one of those three tools to do a DNS lookup the next time the problem happens.
I also agree with another user's suggestion to ping a host by IP address. I would recommend that you do...
ping -n 8.8.8.8
...the -n tells ping not to try to do a reverse DNS lookup on the host you're pinging. 8.8.8.8 is a nice memorable IP address for one of Google's publicly-accessible resolving DNS servers.
As @bmike said, Internet Sharing hides a lot of complexity behind a very simple interface, and some of your questions can't be answered authoritatively without interviewing some of the Apple engineers behind it. But that won't stop me from taking a stab at it...
1) AirPort is different from the other interface types because in order to share over AirPort, your Mac has to actually create the wireless network (as opposed to just providing service over an existing ethernet, FireWire, etc connection). This means that InternetSharing needs to have a bunch of info about how to create the wireless network: network name (SSID), channel, security, etc.
2) Resharing over the same ethernet interface is useful under some circumstances. For example, on my home network my ISP provides limited number of static IP addresses for my use. I run a Mac doing the equivalent of Internet Sharing (actually, I set up the daemons manually as @Spiff recommended) to reshare over the same ethernet. Result: if I put a computer on my home ethernet and config it via DHCP, I get a private (behind-the-firewall) IP address from my virtually unlimited internal pool. If I manually config the computer with one of the public IPs, I get full unfitered internet access, but use up one of my limited public IP pool. Because they're both on the same network, "moving" a computer behind or in front of the firewall is just a simple configuration switch.
On the other hand, if you did this same trick on an ethernet network that already had a DHCP server, computers attaching to the network would randomly get configuration from one server or the other, leading to unpredictability, confusion, and hair-pulling. It's definitely a use-only-if-you-know-what-you're-doing feature. Fortunately, Internet Sharing is smart: if it detects another DHCP server on "its" private network, it shuts itself off to avoid trouble.
3) I don't know of a way to change the private IP range on an IS-created wireless network. On the other hand, it shouldn't really matter, since the network is being created by Internet Sharing, and therefore it doesn't have to worry about conflicts with any existing network numbering.
4) You can add interfaces with Apple's USB Ethernet Adapter. Get some USB hubs, and pile them on!
Best Answer
We had this problem when we provisioned an image taken from another device. It won't hurt anything, but if it bothers you, you can rename it from the UI.
Click the gear drop-down at the bottom of the list, then select "Rename Service"