Potential issue #1 - resolve order
Sounds like a resolving issue around NMB. It's mentioned here in this thread titled: Nautilus doesn't see network computers... [SOLVED].
non-discovering resolve order
reported to work resolve order
# What naming service and in what order should we use to resolve host names
# to IP addresses
name resolve order = lmhosts host wins bcast
name resolve order = bcast lmhosts host wins
Be sure to restart NMB/SMB services once you've made this change.
Potential issue #2 - client protocol
Researching your issue further, I came across this tip in this AU Q&A titled: Nautilus fails to see shares in 18.04. The tip from there was to change the following:
$ more /etc/samba/smb.conf
workgroup = WORKGROUP
client max protocol = NT1
After making the above changes it's advised to reboot, not simply restart.
As part of this tip, make sure that avahi service is running:
$ sudo service avahi-daemon status
$ sudo service avahi-demon start
Potential issue #3 - firewalld
According to this askfedora.org article titled: fedora 27 network browsing doesnt't work. Why? it's suggested to try disabling firewalld. It may be inhibiting the ports 137-139 which are required for Samba's NMB/SMB services to function properly.
Potential issue #4 - Bug 1513394 with gvfs
Continued searches led to this issue that's still listed as open. The issue, titled: Bug 1513394 - Applications using gvfs are unable to browse SMB shares. It has to do with the package gvfs-smb.
Applications using gvfs are unable to browse SMB shares
These steps can be used to see if the issue afflicts your system.
Steps to Reproduce:
1. nmblookup -M -- -
2. nmblookup -M workgroup
4. gio list network://
5. gio list smb:///
6. gio list smb://workgroup
If things don't work the results from the steps above will look like this:
1. will return IP address for __MSBROWSE__ special name
2. will return IP address for workgroup master browser
3. will correctly list workgroup, workgroup members and their shares
4. returned items are missing workgroup members
5. will return empty
6. will return an error message "The specified location is not mounted"
If things are working the results will look like this:
4. returned items should contain workgroup members
5. should contain workgroup name
6. should contain workgroup members
It should be noted that there doesn't appear to be a fix yet for this:
For the record, it doesn't work in Fedora 28 and Samba 4.8 either.
Read the comments on the issue to see the rest of the story.