A broadcast UDP packet would be very easy to do; have your server listen on a particular UDP port for service requests, and when it receives them send a unicast reply with the information needed to connect. Broadcast packets usually aren't routable, so you'll have to make sure the server is on the same network segment as the client. A related idea would be to use multicast, which might put a slightly lower load on your network if it's happening frequently.

Another thought: if the clients pick up their information from a DNS server you have control over, put a record in their default domain pointing to the server. This is similar to how Microsoft's "proxy auto-discovery" works. It's more efficient and survives routing across subnets, but requires more control over the client.