For games with LAN play, the standard thing to do is for the clients to send broadcast packets to discover servers. (The client sends a broadcast, the server sends a direct reply to the client)
In general, the client will send somewhere between three and five broadcast messages, each about a second apart, and will then decide that there must be no server if it hasn't heard any reply within that time. Sending multiple packets makes service discovery a little more packet-loss-tolerant (though that is pretty uncommon on LANs), and having time between them keeps them from disrupting other network traffic too much.
Nobody (to my knowledge) does your option #2, because it will degrade performance of the LAN (or will take quite a while, if you stagger the connection attempts).
But to cope with cases where broadcast is filtered by the local LAN (which is quite unusual, but not unheard-of), most games will allow players to directly enter an IP address to connect to. This allows players in these sorts of situations to connect to a known server, even it they can't broadcast to automatically find it.
For games over the internet, clients will send a direct request to a static meta server, which replies with the addresses for known current server instances. Servers, likewise, contact that meta server to inform them of their own location so that clients can be directed to them. Due to the complexities of NAT, though, this approach usually does not work for servers hosted inside a LAN. This is why this sort of approach is not typically used for LAN games.
Extra side note: It's common practice for internet games to contact a point server first. The point server tells the game on what address it can find the meta server, which will tell it where servers can be found. Point servers are often (though certainly not always) implemented as a simple web server, and are the only piece of this system with an address that is hardcoded into the game. This allows game developers to move their meta server around from one machine to another as required, simply by updating the address returned by the point server. It can also be used to implement a simple form of load-balancing or region-switching by having the point server send users to different meta servers based upon server load or geographical proximity.