If I set up a Roth IRA, I'm going to have to pay taxes on that $31k as income, right? I don't think I could afford to do that.
Correct. Though, you could stagger your conversion over a few years to take the bite out of it.
If I set up a regular IRA, I'm going to lose the tax benefits of a 401(k).
Not sure what you mean by this. A traditional IRA has virtually the same tax benefits as a 401k and has some bennies the 401k doesn't have.
I could just leave the $29,000 from Job B in that account and roll the $2,000 from Job B into a Roth IRA, too. I could handle the taxes on $2,000 much easier than I can handle $31,000 in additional income.
This is an option, though realistically it's almost always better to get your money out of a 401k and into an IRA ASAP so I wouldn't recommend it.
Can I roll both accounts into an IRA and then, whenever I have a job with a 401(k) again, roll the IRA funds into the 401(k)? I doubt it but I thought I would ask.
Yes, you can do that but again, probably not the best idea.
I feel so overwhelmed, and angry because my new job doesn't have a retirement plan (but it was a $20k raise which I badly needed, so...). I am completely lost. I'm 29, so I'm somewhat early in the game of retirement planning, but I don't want to make a huge mistake with this much money. Any advice? I am embarrassingly anxious about this whole mess.
My suggestion would be to roll both of your old 401ks into a rollover IRA at Vanguard or another low-fee/no-load brokerage like Fidelity or T. Rowe Price. The advantage of this instead of keeping it in a 401k is that you get full control over your money and where you can invest it. When you are investing in a 401k you are limited to the company fund selection which can be less than stellar. For this same reason I would not roll this IRA to a 401k if/when in the future that becomes an option.
In the mean time, since you are lacking a 401k it is important that you continue saving for retirement. I would open a Roth IRA ASAP and get on track with contributions to get it maxed out. Also, if you can afford it, I'd start investing in a taxable account. You don't want to get behind just because you don't have a 401k. Especially since you have a nice fat raise to invest with now.
I would also recommend reading the following books so you can learn some basics: The Automatic Millionaire and Investing for Dummies. They're both easy reads and will give you a good base of knowledge. And, of course, keep asking questions.