These guys are right... Access will work on a very, very limited basis, but doesn't really qualify as a true database solution. We use MySQL for our projects, and it performs very well, plus it has the bonus of being free.
There is a second aspect to your question, and that is the auto-discovery. You mentioned you want clients to automatically discover the server without being told where to find it. Someone correct me if I'm wrong, but I'm not aware of a way to do that with MySQL or MSSQL.
In order to achieve that, you're probably going to have to write your own autodiscovery tool. This would most likely take the form of a small program running on your server, listening for broadcasts on a particular port, containing a particular bit of data to identify a requesting client. On the client, you'd want a bit of code to run at the beginning of execution that sends out a broadcast on your network and listens for a reply. When the server receives a broadcast asking for service, it would send back its IP address. The client could then use the IP address to connect to the SQL server. It would look something like this:
Client --- Is there a server out there? ---> Network Broadcast
Server hears network broadcast and gets requesting IP.
Server --- Yes, Here's my IP ---> Requesting Client IP
Client --- Connect to SQL Database ---> Server IP
You'll need to read up a bit on how to create network clients and servers, listeners, and other networking topics, if you're not already aware of how to do it. But the above is the general outline of what would need to happen. After that, your client could just connect to the database using ODBC, like normal.
Good luck!