^Why is it so hard to believe that all the Presidents came from only 5 worlds?
Because 5 is less than 13, and because we already know that those 5 worlds have colony worlds that are considered part of their territory. It's hard to buy the idea that no one from those colony worlds would be ambitious enough and successful enough to ascend to the Presidency but people from the home worlds would be.
Frankly, I also find it kind of hard to think that it would take 70 years for someone from outside the five founding worlds' territories to make it to the Presidency, just as a function of numbers. By the 2230s, you would think that subsequent Member worlds would outnumber the founding Members, and that thus their citizens wouldn't be inclined to only vote for people from those founding Members. (And, no, the experience of the United States's first seven decades isn't applicable to this issue, because the United States wasn't a true democracy until the 20th Century.)
But, hey, it's been established that Madza Bral was the first non-founding Member citizen to be elected President, so the best way to mitigate the mathematical improbability of that idea is to suggest that plenty of the Presidents in those 70 years were from the founding Members' colonies. We might also speculate that some of them were descended from immigrant families -- so, for instance, there might have been, say, a Denobulan citizen of United Earth, born and raised in Buenos Aires, who became Federation President yet was still considered to be from one of the founding Member worlds.
The first 15 US Presidents all came from the original 13 colonies (and only from a handful of them at that), which actually equates out to about the first 70 years of US history.
It's arguable whether or not it's accurate to say that the first 15 U.S. Presidents were "from" the first 13 states. Andrew Jackson, the 7th President, was born in either North or South Carolina (evidence is unclear), but when he became President, he was a citizen of the State of Tennessee, where he'd lived since he was 20 (before it even became a state). And William Henry Harrison, the 9th President, was a citizen of the State of Ohio, though he had been born born in Virginia and had served as governor of Indiana when it was a territory. James Polk, the 11th President, was also a citizen of Tennessee, where he'd lived since he was 11. Zachary Taylor, President #12, started his life in Virginia, spent most of his formative years in Kentucky, gained prominence in the U.S. Army, and was a citizen of the State of Louisiana when he became President.
That does present an interesting question -- might we interpret the line in AotF as including to people who started out on the five founding worlds but later moved to other Member worlds? Might there have been a President who was born on Andor and later moved to, say, Rigel before becoming President?
Since Federation President is an awfully important post to elect someone from a new world to, I would speculate that this indicates that Trill was fairly well-integrated into the Federation by 2230.
Which is hard to reconcile with their portrayal in "The Host" as a species the Federation was still largely ignorant about. But then, a lot of stuff from "The Host" was retconned away by DS9, like the Trill's original appearance, their inability to go safely through transporters, the fact that the personality seemed to come entirely from the symbiont and the hosts were practically zombies until joined, etc.
I'm inclined to just ignore everything in "The Host" at this point. It looks to have been as retconned as what "The Alternate Factor"'s depiction of antimatter.
