Actually, banks cannot be debtors in bankruptcy (11 USC Sec. 109(b)(2) for those who want to see for themselves). I believe that it would be a receivership proceeding under the auspices of the Office of the Comptroller of Currency. I don't know the rules for that, but I assume depositors have the highest priority.
Actually, you have it partially correct. Bank receivership proceedings are conducted under the auspices of the FDIC for any federally insured bank or thrift institution (e.g, savings and loans associations, mutual savings banks, etc). The OCC regulates national banks, like Citibank, N.A., and by statute, must appoint the FDIC as receiver, whenever the OCC decides to "close" a national bank for liquidity/insolvency or safety and soundness reasons.
Insured depositors, of course, get taken out by FDIC insurance. But any uninsured depositor (the amount in excess of your insured coverage) has the highest priority in the claims process, after payment of the FDIC's administrative expenses as receiver.
"Too big too fail" policy has been around since the Continental Bank failure in 1984; by "fail," I think people mean that the bank is placed in liquidation mode, where the assets and liabilities of the bank would be handled under the orderly liquidation/receivership process. The last bank that was too big too fail was Bank of New England in 1991, which drew comparisons, with the failure of Freedom National Bank, a small bank founded by Jackie Robinson, among others, in which the uninsured depositors, including several charitable orgainzations took a hit. Congress mandated that the regulators use the "too big too fail" policy under very limited circumstances, but mega-banks would probably qualify.