So what was the problem? Turns out that iCloud Tabs do not work if you have Private Browsing turned on. This makes sense and somehow my Safari in iOS was set to use private browsing. I don't remember enabling this feature, maybe I tapped it accidentally, but it was set to on.
See the screenshots below that show when Private Browsing is on and when it's off. Set it to OFF if you want iCloud Tabs to work.
Once I turned it off, a few moments later, my Safari on the Mac instantly showed my open tabs!
The interesting thing is it seems that Safari on iOS keeps track of your private and non-private tabs in separate lists, so you can actually flick back and forth between the two.