Honestly, the more I think about it, the more I feel like Sakurai would add Eggman as a boss before making him a fighter. I don't know how big of a Sonic fan he is (he's a fan of all video games, let's be real), but I imagine him thinking that Eggman is at his best when he's piloting a giant death machine and trying to crush Sonic at the end of every zone. In other words, he's too big. LOLOLOLOLOL! He is almost always multiple boss encounters every step of the way in most Sonic games and is rarely made into a playable character. Additionally, Sonic has a plethora of friends who are more prominently playable characters and are fighting Eggman alongside him. To me, it just feels more appropriate for Eggman to be a boss character first, and if there was another Sonic series fighter added, it would be one of his many friends and rivals, and among those, I narrow it down to Tails and Shadow.
Shadow is consistently the most popular. Every time the idea of a new Sonic character comes up, Shadow is always number one. He was the first Sonic assist trophy for a reason. I know a lot of people expected him to be an echo fighter in Ultimate's base roster, but I don't think Sega wants that. They've done a lot to make Shadow as unique as possible while still being a suitable rival for Sonic, so the least he would be is a semi-clone, and not in the way Ken is an echo teetering on the edge of semi-clone. He would be his own character with completely unique animations. He'd be comparable to, say, Wolf who was built off Fox and shares similar fundamentals, but his normals and specials are completely unique.
As for Tails, well... Tails is Sonic's best friend and sidekick. In many respects, he's Sonic's Luigi, the Player 2. I think Mario & Luigi vs. Sonic & Tails would be a really cool match-up. Sonic and Tails are depicted as an inseparable brotherly duo, and I'm sure many fans have fond memories of their adventures in thwarting Dr. Robotnik's evil schemes in the old cartoons. Tails was always right behind Sonic on their journeys, and while he has rarely had a playable role in the past decade or so, he is still Sonic's #1 buddy, always there to support his hero whenever he needs him. While Tails can do a lot of things Sonic can, such as spin dash, the young mechanical engineer could carry an assortment of tools and gadgets to catch his foes off guard. After Brawl came out, I always wanted to see Tails as an assist trophy where he pilots the Tornado and flies around shooting at targets, but that would actually make the perfect final smash for him.
Out of these two choices, I would 100% go with Tails. While I think Shadow is clearly the most popular choice, at least vocally, I don't think it's the right choice to further flesh out the Sonic series. Tails and Eggman are the obvious choices for that purpose, as they have been with the series from the very beginning. In fact, if Tails was DLC right now, his stage could be the Death Egg and would feature Eggman dropping in inside the Death Egg Robot to wreak havoc as a stage boss. They could even throw in Egg Robos and Badniks to disrupt players as they fight, kind of like Pyrosphere where Ridley was a boss and there were a handful of Metroid series creatures littering the stage. I think that would be a fantastic way to properly flesh out the Sonic series and not be stuck with Green Hill Zone and Green Hill Galaxy.
As a matter fact... If they want to cast a wider net over the different generations of Sonic to really flesh out the series representation... If they really want to make me happy... They'll make the stage the Egg Carrier from Sonic Adventure. There can be destructible turrets on the stage, and Eggman can show up in the Egg Viper from time to time to cause mayhem. (Yes, he would be saying "GET A LOAD OF THIS!" very often.) And of course, he is able to be defeated. Eggman is a character that needs to talk a lot, and he'll be talking plenty more as a stage boss than he would as a fighter. Oh my god, I'm already gushing about a reveal trailer idea I'm having. The setting is the World of Darkness. Galeem is fucking dead (thanks Sephiroth), but Dharkon is still alive. The Egg Carrier is cruising through the skies, and Eggman, as he so often does, is using a power much greater than he is to his advantage and is commanding his robot soldiers as well as clone fighters to attack the Smash fighters. The Halberd, the Great Fox, and other relevant airships are all at war against the Egg Fleet from Sonic Heroes, and a bunch of characters on top of the Egg Carrier are fighting their way through the mighty aircraft. Sonic is already fighting Eggman directly, but he's unexpectedly overpowered by a group of cloned Sonics! Things are looking grim for our hero as Eggman charges his laser for one final blow, until... Tails dives in and grabs Sonic in the nick of time! "TAILS FLIES INTO BATTLE!" After the gameplay sequence, Sonic and Tails, with their unrivaled teamwork and coordination, defeat Eggman and his forces and foil the mad scientist's plans once again. All of this happens in tandem with a Sonic Adventure Remake announcement. Totally! ... Please?