OK I actually figured out a fix, I'm using Cloudflare as my domain registrar, and in my DNS settings, my 4 A records that point to Github had the "proxied" type on them, and appreantly GitHub doesn't like that, so I switched from "proxied" to "DNS only" (by just clicking on the word 'proxied'), and it seems to work with my custom domain (without the `www` subdomain). and now the certificate is issued and things are looking good, I hope this helps someone out!
Thanks for the info! I just made the changes on Cloudflare (to DNS only), and will update in a few days and see if it works.
EDIT: yep, that fixed it, almost immediately. If you have any type of DNS proxy make sure to shut it off, because the SSL cert authority is looking for specific A records.
I was having a similar issue. Waiting for 24h hours didn't fix anything. It turns out the problem was that my domain was parked by default (my domain provider is GoDaddy). I removed the parking A record, and 5 minutes later the TLS certificate was obtained. Then I could finally enable the "Enforce https" option in the GitHub pages settings. Then another 5 minutes later, my GitHub pages were online.
TLDR: try to remove the " A @ Parked" record in your domain provider DNS settings and then enable "enforce https" in GitHub pages settings.