Thanks guys, I tried everything y'all have mentioned and still no luck. However, I thought I'd try it on my wife's iPad and boom, connected the very first time and works like a charm.
It must be an issue with my Google Pixel XL phone. @Subwrx300 was having the same issue with his Pixel XL too...