Mine turned out to be a DNS issue. Before figuring it out, I tried lots of other troubleshooting (turning Internet Sharing on/off, restarting all computers, deleting network interfaces). Here's how I fixed it:
- My Mac Mini is running Internet Sharing.
- My MacBook Pro (MBP) is connected to the Mac Mini.
- The MBP could connect to internet content, but not to external content. If could connect to Google in Safari by using Google's IP address (for me it was 188.8.131.52).
- This let me know I had a DNS problem.
- On the MBP, I opened System Preferences / Network / Wi-Fi.
- Clicked on Advanced and went to DNS.
- The address for my Mac Mini was listed as the DNS Server. I instead entered the address of my internet router box that actually connects me to the internet.
- Once I hit OK, my MBP was able to connect to everything again like normal.
The steps I outlined above fix the problem for the single client computer. If you have multiple devices (like your iPhone) connecting to the Mac Mini, you'll have to apply similar steps to each device.
My Mac Mini happens to have OS X Server running on it, so I was able to fix the problem at the source. I turned on the DNS server and told it to forward DNS requests to my internet router's IP address. That fixed the DNS issues for all devices that connect to Internet Sharing.