This is already said, but it cannot be too emphasized: This is not your fault. This is entirely on them. Three months is far too short to evaluate someone even if they were secretly unhappy with your performance. It might be worth talking to an employment lawyer, but likely you'll have to take this on the chin. In the immortal words of the great Captain Picard: “It is possible to commit no mistakes and still lose. That is not a weakness; that is life.”

As everyone has said, you can expect to get questions about it, and I would definitely have a prepared, rehearsed statement. Some recruiters and hiring managers make a big deal about these sort of things, some won't even care. Again: this is not your fault and do not be apologetic about it.

Five weeks is not a lot of time to get a new software job, even in a hot market. This is the unfortunate reality and I would start making contingency plans. If living in NYC remains a goal, then this is a setback but a far smaller one than it may seem right now. You don't have a mortgage or a family hanging over your head. Moving back to NYC will be in play, likely sooner than you think.

Spending time on career development is a good idea. Something with a firm outcome like AWS Solutions Architect is also good. I have the associate certification which I started working on while at Amazon. It hasn't really done much for me, but I'm not seeking positions where it would hold much weight.