I had a financial advisor connected to a bank. I applied for a credit card there and followed up on the rejection at the number they gave. (I might have had to ask the advisor to intervene, not sure.) I got through to the CC people, they asked me a few more questions (previous employment[1]) and then approved one with a low limit. From then on I built a history.

Edit: ah, you’re the OP. Did you have that same issue, where sites would assure you you have a good credit score even as you keep getting rejected on any credit application?

[1] If they lean further on credit reports as a job applicant filter, that could turn into an even worse catch-22!