I just released a DHCP, DNS and Bonjour/Zeroconf library for Arduino with the Ethernet shield.
The DNS library simply looks up IP addresses by host name, but supports a polling mode for non-blocking operation.
The DHCP library is based on previous work by Jordan Terrell, but I added packet resending, an optional polling mode (rather than blocking operation only), some compatibility fixes and the ability to automatically renew your lease before it expires (and rebind if renewing is not possible for some reason).
The Bonjour/Zeroconf library lets you find your Arduino's IP address by a Bonjour name (such as "arduino.local"), resolve other Bonjour names, discover services on your network and even register services running on your Arduino (For example, you can make a web server that will show up in the "Bonjour" bookmarks in Safari on a Mac). Naturally, you need a Bonjour-enabled operating system (such as MacOS X) for this to make sense.
All the libraries as well as their documentation is available at my website. I've also made some examples to illustrate their usage.
If anybody is interested in trying them out, I'd greatly appreciate some feedback.
PS: The libraries are all rather large, but will fit on a Diecimila (DNS and DHCP) or a Duemilanove (Bonjour), even though I personally use them on a MEGA.