The staff at Nintendo didn't even know Byleth was in. Meanwhile, Vergeban knew Steve was coming two years before he did, and considering how he leaked the whole roster precisely saying all veterans are returning, Ridley, Simon, Isabel, Ken and Incineroar would be newcomers, Isaac would be an Assist Trophy, Banjo-Kazooie and Luminary/Erdrick (Hero) would be in Fighters Pass 1, Terry would be the fourth character in Fighters Pass 1, he must be working for Nintendo if he knew who's going to be in the game. Also, discussions about Steve getting into Smash started from Ultimate's development and constantly scrapped.
Oh, and while the idea of Three Houses did start around the time Fates was released, it was put on hold as they developed Fire Emblem Echoes: Shadows of Valentia and only really picked up on Three Houses after Echoes was released in 2017! BOOM! Byleth could not be in the plans for Fighters Pass 1 because Three Houses was in it's infancy at the time and they were working on Echoes. Unless Byleth was the first character concieved for the game, or they jotted down something as generic as "Protagonist of the newest Fire Emblem game," he couldn't have made it on to the plans. If they had planned for a new Fire Emblem character back, Alm or Celica would have been more likely because Echoes was a remake of Gaiden so it would be easier to plan DLC because of the Gaiden source material. Marking down a DLC character from a game that has just been scrapped or delayed in favor of a Fire Emblem Gaiden remake would be a poor decision to make.
And if Steve was planned from the beginning and constantly scrapped due to his complexity and an employee with glasses pushed Sakurai to finally get Steve out as the second fighter of Fighters Pass 2, Steve must be the original fifth fighter. He was supposed to be in the original fighter pass but Sakurai hated working on him so he used a second Fighter Pass to delay him and had a swordfighter from the new Fire Emblem game as an easy substitute. Come on, all the evidence fits better than Sakurai already having a moveset ready for a character that hadn't been developed yet. With Roy, Corrin and Greninja, their inclusions were decided later in their Smash debut's development as past Smash games had their rosters more fluid through development with characters scrapped or added late. In Ultimate's numbering system, Roy was #25, the second to last Melee character. And while Greninja was planned based on concepts, he was revealed after X and Y was released. And DLC for Smash for Wii U and 3DS was planned late which is why Mewtwo and Lucas had trophies, so Fates was developed enough by the time Sakurai decided to introduce Corrin in the DLC. And we all know Bayonetta won an election to get into Smash's DLC.
But when Sakurai decided to make all the veterans return for Ultimate, he vowed no cuts and so he did everything to get all the characters from Smash 4 into the new game, plus the ones who hadn't been seen since Brawl or Melee. It was tough negotiations for the likes of Snake and Cloud. And he decided on what Newcomers should go in, and Nintendo picked out some third-party DLC characters. He refused fan suggestions because the DLC was made with the base roster. And only when Sakurai played Fire Emblem: Three Houses when he struggled with Steve did he change his DLC plans. And at the cost of being forced to do another Fighter Pass which due to it's lateness gave us the ARMS rep that was originally too late to use.
I mean look at the timeline, Fire Emblem: Three Houses was released just four days before Hero came to Smash Ultimate. And then the direct two months later showcasing Banjo's moveset showed a trailer for Terry with Sakurai revealing that more fighters are coming to Smash Ultimate after the then-unannounced fighter. Byleth was revealed in January, the same month he was released and six months after his game. And when Byleth was released, Sakurai revealed the additional DLC fighters afterward will be in a second Fighters Pass containing six fighters. It's a good thing Byleth was shown as the final fighter before the new pass because it would be difficult to find six more unrepped third-party franchises without spirits.
Sakurai said he played an early or pre-release version of Three Houses or something so he’d know how to make the fighter. It is highly likely Nintendo wanted a new FE character when the Fighters’ Pass plans finalized (or began?) in early 2018 (or maybe later 2017 if we assume Sakurai wasn’t including himself when he said the developers didn’t know about the plans until January 2018; Banjo & Kazooie were also negotiated sometime in 2018 so idk), and they knew they could keep DLC going long enough to include the latest FE protagonist.
He didn’t hate working on Steve, it was just hard to make him the way he envisioned. People like to point to a face he made and what he said about Nintendo, but it’s clear something difficult can be tiring even if worth it and he likes it, he was also being humorous, what he said about not just choosing his favorites could’ve just been to assure they don’t just choose his favorites since he loves Minecraft and Nintendo is partly calling the shots, and he and his team put a lot of love into Steve’s contents and his trailer; he even made a short video for Minecraft Live and showed his love for the game a bit during Steve’s and Alex’s presentation.
He could’ve also declined if he didn’t think he could make him; he’s said he can say no if that’s so. Steve was also only confirmed to have been discussed for five years; that could mean they didn’t actually settle on anything until Fighters’ Pass 2 was planned, and according to Imran Khan, FP2 was decided around the time of E3 last year (I think he means the pass itself, not necessarily that the characters were finalized then and there; he says it at 17:02 in this video:
https://youtu.be/58WAbKCJ06A).
And Sakurai wasn’t forced to do another Fighters’ Pass because of characters, but because Nintendo wanted one and he agreed to it. They could’ve just been bonus characters otherwise. The timeline still fits for Byleth to have always been planned as the ending to FP1.
Maybe there was a switch-around, but there’s no good evidence to really support that, which is why most believe there wasn’t or don’t really care (personally I don’t care either way but eh...).
I also highly doubt Steve was so difficult it took more than a year to finish him, or at least not much more. It is very likely the difficulty of the stage stuff, combined with the coronavirus, was just confusing for a good amount of time and possibly why the schedule for character reveals was weird this year.
To put this into perspective, let's compare it to Xenoblade Chronicles 2's development. Xenoblade Chronicles 2 entered development shortly before Xenoblade Chronicles X launched on April 29 2015. Or more precisely, during the later half of Xenoblade X's development in July 2014 as a response to the fans' reaction to the changes. Xenoblade 2 was concieved just two months before Super Smash Bros. for 3DS was released! Fire Emblem: Three Houses started development after completion of Fates which was released in June 2015. Xenoblade 2 was already ahead of Three Houses by a year! And then Three Houses was put on hold while they worked on Fire Emblem Echoes: Shadows of Valentia. Three Houses was going for something new with a school system while Xenoblade Chronicles 2 was meant to be a sequel to Shulk's game but focusing on new characters. Sorry, but it looks like Rex was designed first. Rex was designed before a character in the first Fighters Pass but he got relegated to a Mii costume. It's obvious by the way Byleth looks like he was inspired by Alm from Echoes.
So the year headstart of Xenoblade 2 and how Three Houses started as a Fire Emblem school 3DS game that was put on hold for a Gaiden remake. That just makes it so obvious that if they could have put a Three House rep in the DLC plans, then Sakurai lied about Rex being too late for the roster.
Maybe he lied about Rex, maybe he didn’t. I think it’s worth noting Sakurai and his team likely started on Ultimate planning soon after Smash 4 DLC finished up (according to a translation by PushDustIn, it seems Sakurai actually didn’t even take a break after Smash 4:
https://twitter.com/pushdustin/status/1171812740328869889?s=21). This would include Ultimate’s roster. Perhaps Rex and such weren’t finalized or fully conceptualized by the time the basegame Ultimate roster was finalized, but I don’t know; maybe they were, but Sakurai didn’t like the idea of using early Xenoblade concept stuff for some reason, or maybe FE and Pokémon (Smash 4 Greninja) stuff is prioritized while Xenoblade isn’t pushed as much (or it’s just Nintendo wanted FE, and Pokémon having enough early stuff to work with + new stuff being easy to work in later).
If FE:TH was already in the works or planned for some years, though, I can easily imagine Nintendo plopping down “new FE game” at the end of the FP1 plans since it’d be released a year later and the game was far enough into planning and development for Sakurai to use a lot of concepts etc. and try out before it’s release so he and his team could begin work on Byleth early sometime in 2019.