The alien signal contains a video rendition of Adolf Hitler's speech at the opening of the 1936 Olympics, because this was the first artificial video signal strong enough to be picked up from Vega. The theory is that, although the aliens were able to view the video signal, they "could not possibly" know or understand what any of the contents of the video meant. But if you look at a black-and-white TV signal, it's not at all obvious that it's even supposed to be video information. It's an amplitude-modulated analog of the voltage level to send to an electron gun as it sweeps from left-to-right across a scan line. At the end of every scan line there's a "flyback" indication, which tells the electron gun to return to the beginning of the next scan line. At longer intervals there's another indication which tells the receiver that the field is complete and it should start in on the next field. Oh — and the fields are interlaced: first the odd-numbered scan lines making up the picture are sent, then when that field is finished, the even-numbered scan lines making up the picture are sent. At the time of the 1936 Olympic broadcast, the 525-scan-line frame standard of NTSC had not yet been adopted, and each frame was 180 scan lines high. The only reason the TV sets of the time could decode such a signal is that they were made by the same people that came up with the signal standard in the first place, and contain sophisticated hardware that's intimately aware of what a black-and-white TV signal is supposed to look like. The Vegans would have had no way to know any of these things. What would have made plausible sense would have been for them to send the AM analog back to us in exactly the same format they'd received it. But instead, they send it back as a monochrome digital image, with a bit depth of 1 bit per pixel, arranged into an array whose dimensions are the product of 3 primes. Not only would they have to have interpreted that black-and-white TV transmission — garbled as it doubtlessly was after having travelled 26 light-years — as a video signal, they also guessed correctly that we humans see pixellated images as grayscale!
If you want to get REALLY technical, the TV signal should have been static by the time it reached Vega, and thus impossible to put back together. Some science had to be nudged to allow this plot point, or even to allow there to be a movie.
The Analysis page for Aliens Steal Cable also goes into detail as to why receiving TV signals in another star system is problematic at best and impossible at worst — including the above arguments about format and signal-to-noise ratio.
The discovery about the fundamental nature of the universe that Ellie makes at the very end of the book: That pi contains a message. The implication is that intelligent creatures could manipulate the very laws of the universe, possibly before the universe even existed, to leave a message to any intelligent creatures that emerge within it. The problem is, pi isn't just a physical constant. It's a consequence of basic geometry. Worse, it can be calculated by adding up the terms in a simple, 100% predictable infinite series. To leave a message starting out in the 10^20 digit of pi, you'd have to manipulate the laws of mathematics in such a way that 4 - 1 + 1/4 - 1/(4^2) + 1/(4^3) - 1/(4^4) ... produces this message pattern. Tweaking the physical constants of the universe, such as Planck's constant or the speed of light or Newton's gravitational constant, in such a way that they would produce such a digit pattern might be possible, if you were the architect of universes. Tweaking the value of an infinite series? That should be impossible, no matter how omnipotent you are.
The constant Ellie investigates is not implicitly stated to be pi. One of the aliens makes references to light and gravitational constants. They also give away a pretty major hint; the "God Message(s)" are stated to only be readable in base 11, which enables them to be interpreted as binary code - the simplest way for machines to operate. As for omnipotence, Sagan is stating that it would take such outstanding proof such as this - a repeatable experiment that demonstrates obvious omnipotence - to connect religion with science.