The title says it all, but I have verified setup on nslookup and in the certificate tab of the app. Not sure what to do at this point to get the domain to resolve.
CNAME works just fine. Is there a benefit to using A and AAAA instead?
Well that is actually not working either.
Strange 
You are right in that you can use either CNAME or A/AAAA. Both should work. For a little more about the difference, take a look at Option 1 vs Option 2 on this page:
So assuming the DNS part is correct, the request must be at least hitting Fly’s proxy (that’s what that IP or CNAME points to). And then Fly’s proxy requests a response from your app/vm. If it gets one (as it should), all is well. If not, it will likely return a 502 error. So … it would depend on exactly what error you see. And what HTTP status code (502, 504 etc).
To see if the request is getting to your app, you can run fly logs. That shows the latest X lines and so if you make a request and see some kind of error in there, you would know that’s the issue. All depends where the request is getting to.