Oh, and how does this all fit in with Paul McGann's Shada? I recall hearing a clip where McGann referred to Romana as Lord President (Or a similar honorific)
Let's see if I remember this order correctly ... There are a few stories that lead up to the 50th in the Big Finish range, a title called Zagreus. It's a monster of a story, taking a full 3 cds to tell, and every Doctor and companion who had done work for Big Finish to date (and a few who hadn't yet) came in as various characters. It was the first time Five, Six, Seven, and Eight had been together in a story. There's also a very nice surprise cameo by someone near and dear to all of us Who fans. I won't spoil it for you, and I hope no one else does before you get the chance to hear the story for yourself.
During that adventure, Leela and Romana meet. This is the launching point for the initial Gallifrey series (season), which stars the two of them.
If I'm not mistaken, Romana as the President has adventures with all of the Doctors (Five through Eight). Shada is one of them. As mentioned above, Eight wants an adventure with Romana, so he goes to Gallifrey, grabs her by the hand and says "Let's have tea" then drags her to the Tardis and off they go. Or something like that.
If you keep in mind that they're all time travelers, it'll be a lot easier on you. Trying to figure out where they are in the Doctor's timeline is hard but doable. Trying to do that with Romana as well is probably impossible. Just remember that she's the president for a very long time, up through and including Eight's stories, and you'll be fine.