The below is all just my opinion, but based on alot how JMS talked about the show, its characters and their development. As well as possibilities brought up by other sci-fi fans and magazines/
The last 6 episodes of the 4th Season and the first 6 episodes would have been rearranged in some way. The shadow war would have ended more to the middle of season 4 or later.
The Earth Civil War would have been resolved in the first 3-6 episodes of Season 5, leaving the rest of season 5 to deal with the new struggling alliance, the colony of teeps, and the piracy caused by the Drakh and their centauri masters. I leave the rest for later in this post. In fact JMS once mentioned that the last episode of Season 4 would have been a cliffhanger with Sheridan being captured and interrogated by Clark's Earth forces. (Sound familiar?) I think we would have met Byron late in Season 4 as well. In fact, I suspect that with Sheridan gone and Ivanova in command of B5 and now leading the war effort, she would have hastily let the teeps stay on B5, hoping they could help in the war against Earth. Also, she would be bogged down with being too concerned for Sheridan, leading the war effort and her dead or frozen would be lover, Marcus. Still feeling like she should "boff" someone, she falls for the similar (to Marcus) yet darker, leader of the B5 rogue teeps, Byron.
Lyta becomes one of Byron's groupies, falling in love with him from afar, much the same way Lennier cared about DeLenn.
Byron and Ivanova sleep together and Ivanova's latent telepathic abilites explode. (This is also how I think Byron would have found out about the Teeps Sheridan used in the war to free Earth. Not only that but he would find out about the Vorlons' and Shadows' use of the teeps in their war, info which, of course, will lead to a Teep uprising and Bester's appearance. Bester, sensing Ivanova's newly erupted telepathy strikes a deal with her "just like he did to Lyta in S4" blackmailing Ivanova into abandoning Byron and helping apprehend the rogue teeps in return for keeping her now 'exposed' secret)
Ivanova, now a new telepath, yet new commander of B5 is put in a test of loyaties, eventually sticking with the alliance and telling Byron to buzz off (thanks to Bester's deal), leaving him to kill himself. and Lyta, well you know what she did with Zack and Lochley (now Ivanova)don't you? **Sounds like an interesting Season 5 to me!
I think Ivanova's sudden departure hurt the show very much so. JMS had prepared so much emotional baggage on Ivanova concerning her latent teepness, her role as 1st officer and co-conspirator. the first part of B5 lost so much.
Most of the Ivanova-Byron thing happening after the Earth Civil war and before the Teep uprising. Lyta would still take over Byron's position.
**Remember just some of my opinions. Sorry its all jumbled, but I hope you understand what I was trying to say. I think the rest of S5 would have been the same. We may have seen even more of Mars leader Number One, also.
