It looks like PDF is a marvelous format unless you have a library that supports all of its marvelous features. In which case, it isn't marvelous.
Okular looks like a good candidate for PDF annotation under Linux.
Xournal looks like another option, but may be more complex/less useful than desired.
If you decide to give up on those, one blog author chose to go the Windows-software-under-Wine route.
Other tools mentioned today include Graphviz/Dot, Inkscape, XFig, and Dia.
Presenting Information
I mentioned Tufte (the "Davinci of Data"... mercy) with respect to information visualization. I do want to also mention Scott McCloud ("Understanding Comics"). He has written a fair bit about the authoring of comics. I point this out because comics and graphic novels do such a good job of presenting time-sensitive (process) information in a way that readers can easily follow. As we saw, many of my "failed" diagrams in my own papers are when I tried to capture a process. It seems to have gone poorly in the past.
Scott did the Google Chrome comic, which you may or may not have seen. Although you are unlikely to present a comic in a paper, it is important to remember that human beings are highly visual creatures, and diagrams and images will almost always speak more powerfully than any number of words.
