If you create a new profile and start a new multiplayer game, and make sure LAN is enabled in the Connectivity Menu, does that get the lobby to show up?
Are you shutting down all non-essential programs before starting the game, especially anti-virus and anything network related (utility or monitoring programs, etc)?
If you each try starting 2 instances of the game, does anyone have a problem seeing or joining their own LAN lobby?
Start the game, switch to windowed mode and lower the game resolution (and maybe mute the sound volume), start a multiplayer game, hit Esc, open the Connectivity Menu, optionally disable online multiplayer (if it is enabled) and make sure LAN Connections is enabled (or that can be done in the options before starting a new game).
Next, start the game again from the 'EoCApp.exe' program file (doesn't matter if the first instance is started through Galaxy or the executable), select Join Online Game in the Campaign section, switch to the LAN tab, rather than Online, and if the lobby is listed, try joining.
Try resetting your network adapters:
- click Start (or Search in Win 10), type cmd into the search box, right click Command Prompt and select run as administrator.
- type the following command and hit Enter
netsh winsock reset
- when that is done, there should be a message 'Winsock reset completed successfully'
- type exit and hit Enter, then reboot your computer.
For more details, see: