Apple - Disabling Preview's "sliding" animation

You can use ⌥ + ↓/↑ or ⌥ + ←/→ to navigate pages without the sliding effect.

As a workaround - use Skim. It has better tools for full-screen presentations anyway.

http://skim-app.sourceforge.net/

Note - native Lion full-screen doesn't work yet, but the non-native fullscreen works fine.