The refilling of the exchange tanks is done by the propane company, not Walmart or whoever has the service, so theoretically the tanks should be full.
I don't know about NY, but here there's quite a price differential. At the exchange, it costs ~$22 for a full tank with exchange of an empty. If you don't have a tank to exchange, you need to initially purchase a full one for ~$44.
I purchased an empty tank at Costco for ~$25 (Home Depot has them for around $35), but it only costs about ~$11 to refill it at a local hardware store.
One other suggestion: always make sure you have a back up - either a small tank or, for a 2 burner stove or portable grill, a couple of 1 lb. bottles. Invariably your main tank will run out in the middle of cooking at some point. If you're doing the exchange route, then avoiding this scenario means that you're loosing a bit since you're going to exchange with some fuel left in the tank.
Yes, they should be full, but "full" is relative. You can't put 20lb into a 20lb tank with the OPD, so they only fill to 18lbs or so, at least in my limited experience getting a tank refilled. I don't have direct experience with Walmart, but there are a lot of complaints against WM and supplier Blue Rhino, as well as AmeriGas, about only have 15lbs in their tanks. There's a class action suit against the two companies.
So yeah, I would get it refilled now, but back when I was exchanging tanks, I didn't think much about how much was actually in the tank. It was much cheaper back then as well.
The spare bottles are always a good idea.