We're adding an 'accept cookies' GDPR banner across the bottom of our site.
Should it be the first thing that gets focus when tabbing into the page?
Yes it should be the first item that gains focus, even before 'skip links'. It is the only use case I can think of where 'logical tab order' does not apply.
Also you must inform a user what cookies your page uses, including essential cookies. You must also let them edit their preferences and make sure you tell them where and how they can do this once the accept. This all has to be done when someone first lands on the site.