The rules for both variants are available at FFG's site, so you can read them for the full details. Both expansions contain an "alternate ending" which can replace the Kobol objective, kicking in when the fleet jumps to distance 7. Both have new character and skill cards. Both expansions include the possibility that characters will be executed, not just brigged - it's a bigger feature in Pegasus.
Summary first, then discussion:
In general, this expansion adds a lot of "tweaks" to the gameplay; once you've got it, you'll probably use most of the new rules every game.
New characters: Admiral Cain, Ellen Tigh, Kat, Dee.
New cards: Lots of new and interesting crises, and most of the new skill cards are in this set. There are an additional 1,2,3,4, and 5 card for each skill deck, with some useful new powers. Compensating for this is the new "Treachery" skill, which only goes from 1-3 but is always negative, and has special text only usable by cylons. Unfortunately it's not safe to discard either, as some booby-trap Treachery cards can hurt the humans if you do... Anyone drawing treachery is good news for the cylons. (And some new crises can force you to draw treachery.)
Major new rule: Pegasus. The humans get an extra battlestar board with four new locations. This gives the humans more effective guns against raider swarms, and another way to hurry up jumps. It also adds the lethal "airlock" location - don't want to try to brig that suspect? Just kill them! Of course, a good cylon player can con people into executing other humans...
(This variant makes "destroy Galactica due to damage" cylon win nearly impossible, because the humans can soak 4 extra hits on Pegasus if need be.)
- Minor variant: Cylon Leaders: Cavil, Leoben, Caprica Six. These are playable characters, replacing one cylon loyalty card. Effectively, they work like revealed cylons from the start, but can "infiltrate" and rejoin Galactica, playing cards as human crew. They draw an "agenda" describing which team they have to support to win, but it also has a limitation - they mustn't win by too much.
(The idea was to replace the uncertainty of "I don't know who's a cylon" with "I don't know which side the cylon is on". In practice implementation isn't perfect, and this variant reduces the uncertainty.)
- Variant ending: New Caprica. Instead of ending after a jump from distance 8, at distance 7 the fleet lands on a "New Caprica" board and is occupied. They then have to take actions to release the civilian ships from lockup while waiting for Galactica to jump back, then defend them while evacuating. Crises are drawn from a new deck of 'during the occupation' crises.
(This definitely favours the cylons, as it's harder than just making one extra fleet jump. If the change from 8 to 7 even saved you one. However, it's hardest if fleet attacks have been light, because there's more civilian ships left to protect, so it evens out a bit.)
Fewer tweaks to the game, but several major new variants.
New characters: Sam Anders, Tory, Gaeta, Cally.
New skill cards: Some 0 cards for each deck, which have some other effect on the skill check when played. (e.g. the 0 Tactics causes two extra Destiny cards to be played in.) One 6 card for each deck, with special text so good you want to play it for that instead of the 6. (For example, Engineering 6 can be used to build a new nuke.)
New crisis cards: A lot of interesting crises that play off the new rules. There are no new fleet attacks, so if you don't play the Cylon Fleet variant, you'll be sharply reducing the proportion of fleet attacks in the deck if you use them.
Major variant: Cylon Fleet. There are no fleet attacks. Instead, cylons build up forces on their own fleet board with it's own jump track. When the cylons jump, they arrive en masse on the main board. When the fleet jumps, surviving cylons move back to their board to build up for next time, but civilian ships are not removed. They can be escorted off by vipers instead, but that uses up precious actions. Humans get an extra title, CAG, which helps command unmanned fighters, as well as some better Vipers.
(This evens out the randomness of fleet attacks, but with competent cylons can make the buildup of raiders harder to deal with in the endgame... by the end most of the civilian fleet could be on the board. Works better when used in conjunction with the Pegasus; otherwise the humans can be a touch outgunned. You will need your nukes.)
- Variant ending: Ionian Nebula. This changes the game by making much more use of the cast of characters. As well as the characters in play, you have random extra characters all over the ship, and a limited supply of "Trauma" tokens used to decide whether they do good or bad things when encountered. At distance 7 you enter the Nebula and there's an extra round of personal crises (an extra random dilemma to face) and possibly executions, depending on how well you've done at getting rid of your 'bad' counters.
(So this variant emphasizes character interaction more, and gives you a whole new set of possible suspicious behaviours to indulge in. Properly managed by humans it can result in a lot of extra fleet bonuses... but needn't.)
- Minor variants: Conflicted Loyalties / Final Five. Characters have additional personal goals that they have to accomplish to win. Final Five Cylons, if used, also go in the "Not a Cylon" loyalty slots - they count as being on the human side and work like humans, but they make it much less safe to use 'peek at loyalty card' abilities.
(This variant makes life much harder for the humans, as they're wasting resources and suspicion dealing with extra side issues.)
There's plenty to like in both sets. Which is "better" depends a bit on what you like most about Galactica, and especially on what you like least.
If you like the treachery/uncertainty, but play 4 or 6 player and think the weak "Cylon sympathiser" mechanic is a major flaw, get Pegasus.
If you dislike the random distribution of fleet attacks, and want to avoid games where there are very few or very many, get Exodus.
If you think the series cast should appear more, get Exodus.
If you don't play often, you'll get more out of Pegasus, as Exodus has fewer 'every game' rules changes and more major variants.