Additional info: I'm trying to do a Mega Backdoor Roth and not sure if I should open a Rollover IRA or Traditional IRA (with Fidelity) to deposit the check for any gains.
Money contributed to and withdrawn from those is treated identically by the IRS.
At one time, only money that had been "rolled over" from an employer plan to an IRA, and associated gains, could then be rolled back into an employer plan. The IRS will now allow money from any traditional IRA to be rolled into an employer plan, but some of those employer plans retain the "only from a Rollover (aka Conduit) IRA" restriction.
So it probably doesn't matter, but given the choice a Rollover IRA provides a theoretical advantage. Often the taxable portion of an MBR distribution is small enough that you might as well put it all into Roth and pay tax on the taxable portion.
If the taxable portion is sizeable, and your employer plan allows, you could distribute into the Roth and Rollover/Traditional IRAs as applicable, then roll the taxable portion back into the employer plan. This avoids the immediate tax on that amount, and avoids pro-rata issues on that amount should you wish to use the "non-mega'" backdoor Roth.