When I open a document, Evince remembers that the window was fullscreen last time, and resizes it. However, it does so only once the window has already been shown, which does not look really nice. From the Gnome HIG:

http://library.gnome.org/devel/hig-book/stable/windows-properties.html.en#windows-show-hide

"Always show a window as soon as possible, but make sure your window is the correct size before displaying it. Resizing a window after it is visible is disorienting and gives an unpolished look to your application."