As far as moving costs are concerned, pay attention to if they charge you mileage and time from their office to where you are moving from. One of the places I got quotes from for doing an in town move did this, and it added around $100 to the quote, making their high quote even higher.
A move like this is a good time to sell off crap you don't use anymore, or can be easily ad inexpensively replaced later on. We sold off a couple of extra TVs, some lawn equipment, a bed, and a couple of pieces of furniture and a bunch of other assorted junk before coming out here. We were fortunate that some family members offered to hold onto a few pieces for us until we moved into a place with more space. My brother in law ended up getting a free rental of a 60 gallon air compressor for two years as a result.
There is no problem in getting change of station leave as there was in times past here. Not to say you couldn't eventually get it, but the training department was rather inflexible about your arrival date and the amount of time given to get your maps drawn and some other CBIs done once you got here. Now, if you want to take it on the front end, they have no issues with it and the timer for your maps and tests don't start until the day you get here.