People often ask critics of BSG's ending how would they have ended it instead. Here's a blueprint for the shape of things which should have been.
You have to go back pretty far to undo the ending properly.
Here's how it could have been done.
Season 2
We start by not killing Admiral Cain in Resurrection Ship, Part 2. Instead, Gina merely escapes the Pegasus with Baltar's help. In the episodes following, Cain meets with Roslin as planned and eventually Helo and Tyrol are freed when Roslin pardons them. Then, Roslin dies. Yes folks, it's hard to hear, but Roslin should have died. It's a tough thing to say because she's a fantastic character and Mary McDonnel is a marvelous actress, but BSG was a progressive show and Roslin is a stagnant character by the end of season 2.
Roslin's death would leave Baltar as president and Cain in command of the fleet indefinitely. Adama would be mighty pissed, but unable to do anything about it. Now imagine a stretch of episodes where suddenly Admiral Cain and Baltar are the main characters of the show instead of Adama and his crew, much like how during the sixth season of Star Trek DS9, the key figures of the Dominion usurped the Federation characters as the main characters of the show during the occupation of the station.
In Downloaded, Caprica Six never experiences "Head Baltar." At no point in the series does Head Baltar appear and the Six in Baltar's head is later revealed to simply be a chip placed in Baltar's head by Caprica Six just as he suspected. They are not "angels from god."
Cain, with her ambiguous moral center, would continue to exert a destabilizing influence on the fleet throughout season 2, though less so as the season goes on as Adama and Baltar settle into uneasy but functional working relationships with her. The season 2 finale stays mostly the same, except Baltar is reelected instead of elected for the first time and the stupid plot thread involving Baltar giving Gina the nuclear bomb never happens. Instead, in the final moments of the season 2 finale Gina suicide bombs the Pegasus CIC using a conventional bomb, killing at least herself, Cain, and Fisk.
Settlement of New Caprica still happens mostly the same way. Baltar promotes Adama to admiral since Cain is dead and Adama promotes Apollo to commander of Pegasus at this time. Instead of Cloud Nine blowing up (since Gina suicide bombed the Pegasus CIC), the D'Anna Cylon (you know, the one the writers forgot was still in the fleet?) sends a covert radio signal attempting to contact the Cylons to alert them to the fleet's location.
Season 3
One year later, the Cylons receive D'Anna's signal and the New Caprica story arc could easily play out much the same way, except no blowing up the Pegasus. Instead of kamikazing the Pegasus to escape from New Caprica, Colonial One is kamikazed instead (potentially resolving the show's reputed budget problems with having too many sets and allowing the Pegasus to remain in place of the Colonial One set). Baltar then ends up with the Cylons just as season 3 depicts. Tom Zarek becomes President.
A Measure of Salvation still happens, but the Colonials don't wuss out. They succeed in infecting the Cylons with the virus and Helo isn't allowed to interfere. As the Cylons are dying around him, Baltar cures them using Hera's blood before they all die out. This elevates Baltar and Hera to the status of messiah to the Cylons. The Eye of Jupiter storyline plays out much the same way. Baltar returns to the fleet as a prisoner.
Starbuck dies in Maelstrom. She doesn't ever come back. She's not a supernatural being.
Baltar is found guilty at his trial and is sentenced to death. Commander Lee of the Pegasus opposes the death penalty for Baltar and believes he should face life imprisonment instead. He kidnaps Baltar, imprisons him aboard the Pegasus, and prevents anyone from getting access to him to execute him. Admiral Adama orders Lee to surrender Baltar. Lee refuses. An armed conflict ensues between the Galactica and Pegasus. During the battle, the Cylons attack (paralleling Resurrection Ship, Part 1) and the battling Adamas call a temporary truce to deal with the Cylon attack.
Season 4
Lee and his father are never quite the same around each other ever again, since having crossed the line of opening fire upon one another. They are not on speaking terms and deal with each other through intermediaries. President Zarek assumes a more prominent leadership role as he directs the fleet's search for Earth. The search for Earth in season 4 is based on archeological evidence (like the Temple of Five and the Eye of Jupiter) rather than mysticism as was aired.
The devastated Earth discovered in mid-season 4 is the real Earth. The show is set in the future, not the past. Earth is truly a nuclear wasteland.
Archaeological evidence on the devastated Earth reveals the identities of the final five Cylons. Faced with no promised land to flee to, the Colonials realize that peace with the Cylons is their only salvation. With prominent characters like Tigh having been revealed as Cylons, peace looks much more appealing than before.
An offer of peace to the Cylons divides them. A small rebel contingent breaks away from the Cylons and joins the Colonial fleet in an effort to reconnect with the Final Five. The Cylon hard-liners (led by Cavil) refuse peace. They also hold the only resurrected copy of Ellen Tigh hostage.
The combined forces of the Colonials and the Cylon rebels make a final assault on the Cylon homeworld (the "colony") to free Ellen and end the war. After defeating the Cavil faction, the Colonials make peace with the remaining Cylons.
Since the best available habitable planet left that they know about is Kobol, they resettle it. The Sacred Scrolls said that Zeus warned the leaders of the tribes that any return to Kobol would carry with it a cost in blood. It certainly did. But the surviving humans and Cylons are resolved to make it work this time. All of this has happened before, but it doesn't have to happen again. Only time will tell whether or not the thirteen tribes can live in peace again...
There is no second Earth, god is not real, and no supernatural bullshit occurs.
So say we all.