So, I am not going to get too excited yet as it has been just two days, but I may have finally fixed this problem.
I think the problem was my jailbroken iPhone 3G! I didn't have many Cydia apps installed. I had SBSettings, Cycorder, GV Mobile, StatusNotifier, PirvaCy, Backgrounder, Five Icon Dock, PDANet, and TV Out installed.
Once Qik came out and I found out that VoiceCentral is coming out with a Google Voice web app very soon (not to mention that I can use Google's Web Page, as crappy as it is), I figured I could live without the other stuff and go back to a non-jailbroken iPhone. I do miss SBSettings and StatusNotifier, but other than that, it has been fine.
I un-jailbroke my phone two days ago and I have not had an issue with the self-assigned IP address on any of my Macs or my iPhone since then. Now I have had streaks like this before, but in the couple of days before this, my iPhone was getting the problem several times each day. And things that would have normally given me trouble, like turning on my iMac or adding a new device to the network, have worked just fine.
But that is not all...I see that I first posted in this thread August 8th of last year, so I went back to see when I first jailbroke my phone. Guess what? I downloaded redsn0w on August 1st of last year! It seems like too much of a coincidence to me. Well, that and the fact that I tried all of the suggestions in this thread, replaced my router, and had this problem in both 10.4, 10.5, and on iPhone. It makes perfect sense. The jailbreak was the only thing that changed when this started happening. And these are the only Cydia apps I really use and have been using them since I first jailbroke.
So, I'd suggest that if you have a jailbroken iPhone with some or all of the apps that I had installed and you have this problem regularly, see if restoring it to non-jailbroken software helps. I don't know if it is one of the apps I had installed or the jailbreak itself that gave me trouble, and frankly I don't care.
I'll post again in a couple of days if things are still working. And since the un-jailbreak is the only thing I have changed, I won't change anything else until I am sure everything is working OK.