I want to add this here, in case someone else comes looking. The issue with network discovery is the old way and was tied to SMB1. The new way, WS-Discovery does not yet appear to be implemented in SAMBA. Windows does not yet support Zerconf so AVAHI does not work for Windows.

Falling back to SMB1 while disabling SMB2/3 is not the answer.

Someone named stilez wrote an article describing the situation here.

And the article provides a link to a python script wsdd.py, which provides the missing functionality. Running the script caused my SAMBA AD servers to instantly appear on Win 10 boxen.

EDIT:
Script is now available under Debian/Ubuntu repository:

sudo apt install wsdd

I had configured the share to not use a password

Samba does not actually support per-share passwords. This security model was used in the Windows 98 era, but was completely removed from Samba in 2012. (Meanwhile Windows NT/2000/XP series never had per-share passwords in the first place, they were account-based the whole time.)

All SMB security is now account-based (just like in SSH and other protocols) – you provide a username and password to log in to the SMB server, and then access to shares is granted depending on your user account.

so I believe that it wanted a password to connect to the Linux machine

That's almost right.

By default, Samba indeed uses the same system accounts as Linux itself does. The only difference is that the passwords are stored separately – Samba needs to store a NTLM-compatible password hash, as it cannot use the standard Linux hashed passwords.

This means that you must set a "Samba password" for your Linux user account before you can connect – use smbpasswd to do this on the Linux server:

sudo smbpasswd -a jonathan

(The Samba username always needs to match your Linux username in order for file permissions to work correctly, but the passwords can be different.)

I have set the necessary port access in UFW namely 137/udp, 138/udp, 139/tcp, and 445/tcp.

SMB runs over 445/tcp alone. (Unless your client is running Windows 95/98, which needs 139/tcp.)

Port 137/udp is used for LAN hostname resolution (NBNS) and port 138/udp is used for nearby computer discovery ('Computer Browser' service) – both are completely optional for SMB, and in fact both are NetBIOS-based services which most Windows 10 clients have disabled along with disabling SMBv1.

The problem is not the Samba share but a new security setting under Windows 10. They specifically made it so that you cannot bypass this behaviour from the Samba side. They explain why under the section Cause.

Symptoms

In Windows 10, Windows Server 2019, or Windows Server 2016, the SMB2 client no longer allows the following actions:

• Guest account access to a remote server.
• Fall back to the Guest account after invalid credentials are provided.

SMBv2 has the following behavior in these versions of Windows:

• Windows 10 Enterprise and Windows 10 Education no longer allow a user to connect to a remote share by using guest credentials by default, even if the remote server requests guest credentials.
• Windows Server 2016 Datacenter and Standard editions no longer allow a user to connect to a remote share by using guest credentials by default, even if the remote server requests guest credentials.
• Windows 10 Home and Professional editions are unchanged from their previous default behavior.

If you try to connect to devices that request credentials of a guest instead of appropriate authenticated principals, you may receive the following error message:

You can't access this shared folder because your organization's security policies block unauthenticated guest access. These policies help protect your PC from unsafe or malicious devices on the network.

and

Cause

This change in default behavior is by design and is recommended by Microsoft for security.

A malicious computer that impersonates a legitimate file server could allow users to connect as guests without their knowledge. Microsoft recommends that you do not change this default setting. If a remote device is configured to use guest credentials, an administrator should disable guest access to that remote device and configure correct authentication and authorization.

Windows and Windows Server have not enabled guest access or allowed remote users to connect as guest or anonymous users since Windows 2000. Only third-party remote devices might require guest access by default. Microsoft-provided operating systems do not.

and

Resolution

If you want to enable insecure guest access, you can configure the following Group Policy settings:

• Open the Local Group Policy Editor (gpedit.msc).
• In the console tree, select Computer Configuration > Administrative Templates > Network > Lanman Workstation.
• For the setting, right-click Enable insecure guest logons and select Edit.
• Select Enabled and select OK.

Source

https://docs.microsoft.com/en-us/troubleshoot/windows-server/networking/guest-access-in-smb2-is-disabled-by-default