...from what I've read most NSAs go straight to Pensacola while they wait to start school instead of working at their local recruitment center. If that's the case, how does getting set up with a rental unit typically work
When you first show up, if you're single, you can crash in the BOQ where you'll get your own motel-like room. If you're married you can go to the Lodge. If those are full, you can get a Non-Availability which will authorize you to get a room in town within a certain price limit. From there you can start looking for rentals.
There's some nuance to this process that ensures you won't lose money in the process, but you'll learn about that stuff at a later date.