Typically, bypass blocks (WCAG 4.1.2), or "skip to main content" links, are at or near the beginning of the DOM so that keyboard and screen reader users encounter them first before any of the page's content.
The new cookie notice is a temporary thing (once the user accepts or denies the cookie use) and will hopefully be never be seen again once acknowledged. Because their appearance is temporary, putting them before any bypass blocks makes the most sense.
If the notice is after the bypass block, then a screen reader user might not find it because they'll jump over it to the main content.
If the notice is in the footer, then a screen reader user might not find it because they already found what they wanted on the page and have moved on. Sometimes a user will stick around and navigate all the way through the footer, but that typically only happens if they haven't found what they're looking for.
While you could have the notice at the beginning of the DOM and use CSS to visually place it at the bottom of the page, low-vision and cognitively impaired users might have trouble with that. They'd see the focus indicator jump to the bottom of the page to the cookie notice, and if they're using a screen magnifier, the page viewport will move to the bottom of the page, and then further tabbing will jump the focus back to the top of the page. It's a bit jarring. And if they continue to tab through the page to the footer, they'll navigate through the footer, visually see the cookie notice after the footer but the focus will jump over it.
Once the cookie notice is accepted, then the "skip to main content" becomes the first element in the DOM again.
