The Arecibo Interstellar Message (AIM), sent in the direction of the globular cluster M13 in 1974, was the most significant attempt to deliberately establish communication with extraterrestrial civilizations.  Previously, messages had been sent physically attached to spacecraft:  Pioneer 10 and Pioneer 11.  Afterward, similar messages were sent on Voyager 1 and Voyager 2.  But physical messages propelled into space, when compared to radio signals, are relatively equivalent in effectiveness to messages put into bottles and set adrift in the oceans, when compared to telephone calls.  As much an improvement as the AIM was over the Pioneer and Voyager messages, it could still have been designed more effectively, as most things can in hindsight.
        I believe the biggest obstruction to understanding the AIM is its reliance on mathematical universalities, primality in particular.  Prime numbers are of no practical use, and are more an intellectual curiosity than an interspecies Rosetta Stone, popular science-fiction culture to the contrary.  The AIM used "on" and "off" pulses to signify "1" and "0", and from there to signify the actual message.  Ostensibly, the extraterrestrials who intercept the AIM will realize the importance of the number of bits (1679) in the message, and deduce from it that they should arrange the bits in a 73-by-23 array (the two numbers being primes and the only non-unity factors of 1679 other than itself).  But as the AIM is written out, the first six bits are "off" pulses, which are defined as "the 'off' interval separating two of the 'on' pulses" (Goldsmith, 476).  Obviously, an "on" pulse is required at the beginning of the message; otherwise, the "off" pulses at the beginning will be undefined.  The intercepting aliens would have to add the appropriate number of the appropriate type of bit to the beginning of the message to be able to properly format it at all.  The AIM should not be as open to interpretation as a horoscope.  This problem can be eliminated by explicitly beginning and ending the message with one or more "on" pulses to properly bracket it.
        In designing an interstellar message, we must take into account the "alienness" of the interceptors of the message, and ensure we do not make unreasonable assumptions about their abilities.  We must necessarily endeavor to make the message as understandable as possible, and not fall back on appealing to superior alien intellects to decipher the message, just so we can justify sending complicated information.
        A better use of the message would be to convey one thing in as many different representations as possible, effectively hedging our bets.  The AIM takes the alternative of sending a lot of information with the trade-off that the message becomes correspondingly more difficult to decipher.  We would hope for this message to prove effective the first time it is intercepted; if the odds favor us long enough for another civilization to actually receive the message, the worst thing that could happen would be for them to ignore it or to be unable to decipher it.
        The creation of an interstellar message is as much, if not more, in the domain of semioticians as of astronomers, who would provide the subtext of the message, but would not be as adept at conveying it.
        Building off the AIM, we can omit the drawing of the Arecibo dish, as it does not add anything particularly valuable to the message.  We can also leave out our location in the galaxy, which (as pointed out by Carl Sagan) can be derived from studying the specifics surrounding the message's reception.  In general, the ideal message would be less number-dependent and more semiotic in nature, less like the representations of nucleotide bases and more like the diagram of the solar system (as depicted in the AIM).
        I propose to change the shape of the signal's two-dimensional representation to that of a filled circle.  This would remove the reliance on prime-number-recognition to form the proper size of array, since it would itself be realizable in only one way, that which forms a (relatively) perfect circle.  While not being as economical as the AIM, which was so primarily to accommodate the prime number arrangement, it would stand a better chance of being correctly reconstructed.  We know there is no inherent problem in a "round" message, since that is precisely what the gold-anodized records on the Voyager spacecraft carried on their jackets.
        Further, a circle would be the next most natural shape in which to assemble the bits (after a line), since circles are a far better intragalactically-known shape than are rectangles—the "water hole", if you will, of the visual medium.
        The circular format would remove the length constraint, allowing possible messages of varying sizes to be created, i.e. making the presentation fit the message, as opposed to vice versa, as with the AIM.  Thus, the optimum presentation can be designed.  The variable (during creation) size allows for the inclusion of more pictures, which are more information-dense and more resistant to degradation than are binary numbers.  There is only so much which can be expressed numerically, and doing so makes unfounded assumptions about reading conventions, and places restrictions on the way the message must be viewed that simply do not apply to pictures, which manifestly can be viewed holistically.
        The pictographic approach sets an interpretive standard, so that everything in the message can be read in a single fashion; in the AIM, one string of digits might be intended to represent an abstract numerical value, an element, a planet, a human being, an arrow, a radio wave, et cetera.  Correct translation of a message requires the correct interpretive framework, and the correct translation of the AIM requires one to alter that interpretive framework several times—surely a barrier to communication.
        Since aliens would know of the "water hole" and thus of water, we could take advantage of the preexisting epistemic relationship to represent other elements by specifying a symbol—say, a small, open circle—and linking it to a depiction of hydrogen, then performing additions on that symbol, using it to signal that the corresponding depictions are of other elements.  Of course, in the pictorial message proposed here, the atoms of individual elements could simply be "drawn" in some conventional manner, instead of numerically designated.
        All the things left out of the AIM (e.g. dish, location, etc.), combined with the extra space attained by the loss of the prime-number restriction and by the variable size of the message, all allow for us to transmit as much information, as clearly represented, as desired.

Goldsmith, D. and Owen, T.  The Search For Life In The Universe.  New York:  Addison-Wesley Publishing Company, 1992.

Information used from the above source includes the three different views of the Arecibo Message (and the explanation and justification of it), the "water hole", and the Pioneer and Voyager projects.

Sagan, Carl.  Cosmos.  New York:Random House, Inc., 1980.

Information used from the above source includes the colored view of the Arecibo Message (and the explanation of it), the applicability of the Rosetta Stone, and the fact that our location can be derived from the direction (etc.) from which the message was received.

"Ask Dr. SETI:  The Arecibo Message".  World Wide Web, <http://www.setileague.org/askdr/arecibo.htm>.

Information used from the above source includes the recommendation to see Cosmos for information on the Arecibo Message.