I am moving to the UK for a job in the next few months. This job is for the US government and they will be paying me in USD. The vast majority of my expenses will be in GBP. Is there an easy way for me to convert direct deposits every month from USD to GBP with little-to-no fee?
Exchanging money will always cost you something. There's no hard and fast rule for minimizing associated costs and there's no surefire trick. Minimizing your cost depends on how much money you want to exchange and how fast you need it where.
The only real 'trick' is to exchange your USD for the GBP of someone who's going to need USD. You can bypass banks and money exchanges and agree on a rate halfway between buying and selling.
Here are a bunch of suggestions.
Electronic exchanges (getting money from an ATM in the UK) are generally cheaper than cash exchanges. However, this depends on your bank.
Don't exchange at airports. They typically give you bad rates and charge commission.
High street (legal) money changers tend to be comparatively reasonable with their rates.
Depending on your bank and credit card company, paying as much as possible with your credit card might be financially advantageous.
In your situation, the lowest-cost option could be to use a currency exchange specialist like xe.com. I believe they can EFT (ACH) the money from your US account, and send it to a UK account. There may be other companies that can do the same. Currency specialists like this have better rates than most banks. This assumes you can open a UK bank account, which can be difficult for a new resident (especially for an American, because of the additional paperwork to comply with US laws like FATCA).
Another route, which can actually be not that much more expensive, is to pay for as much as possible with a US credit card that has no foreign exchange fee (such as some of the better Capital One and Chase cards). That way, you'll get a reasonable exchange rate, and effectively just change money as you need it (so averaging out exchange rate fluctuations). Especially try to put your rent and utilities on a card (be sure to tell the card issuer you're going to use it in the UK). This may not always be possible, as some may only accept UK-issued cards, but it's worth a try.
Some cards will allow you to put the card into credit (via a transfer from your bank account, online), and then draw it out as cash without fees, but check your card's terms carefully.
You can also use a debit card to withdraw cash, but it's hard to avoid fees. Charles Schwab bank (and brokerage), and Citibank (if you can access a Citibank ATM near your UK location) are among the few options. When paying in a store with a debit card, you can ask for cash-back (usually up 100 GBP) which gives you more cash without a separate trip to an ATM and the ATM fee.
Finally you should of course check with your employer (US government). They may already have systems in place to issue you with local currency at a good rate, or may have an in-house exchange service.
Note: Usually peer-to-peer currency exchanges like Currencyfair.com have a better exchange rate and lower costs than even the specialist currency brokers like xe.com, but in your case they're unlikely to be suitable. They currently don't accept US persons as customers (due to FATCA etc), and to get the money to them would require a domestic wire from your bank (which you'll probably find hard to arrange from a distance, plus there's a cost).
One trick I've used to migrate Australian dollars to UK pounds is to use paypal to deposit dollars and then withdraw it in pounds. I used two paypal accounts, one on the Australian paypal site linked to my Australian bank account and one on the UK site linked to my UK bank account. I then sent the money accross the two paypal accounts. I don't think there are any upfront fees and I'm not sure how they calculate the exchange rate. I haven't done this in a while but from memory the transfer is not instant.
@Gagravarr in the comment has pointed out that there are fees in PayPal transferrs which can be found at https://www.paypal.com/uk/webapps/mpp/cross-border-and-conversion-fees#currencyconversion
Many banks offer multi currency accounts. This is a nice description of a multi currency account offered by Citibank, but other big banks have similar accounts. From my understanding of multi currency accounts you can make a deposit in any of he supported currencies and you can make a withdrawal in any of the supported currencies and they take care of the exchange. Of course they are making money on this, but it offers flexibility over keeping a USD account and having to make international wire transfers on a weekly/monthly basis.
When I did something similar, I arranged for my company to pay my salary partly in my home country (UK) and partly in my work country (Canada). Since this is an expense incurred because of the job that your employer has sent you to do, it's not unreasonable that they bear the expense of converting currency. And moving money around like that is soemthing the US government does all the time.
With that setup you should find minimal necessity to change currency. You might also consider charging your exchange fees to your employer as a business expense.