Disabling Preview's "sliding" animation
Solution 1:
You can use ⌥ + ↓/↑ or ⌥ + ←/→ to navigate pages without the sliding effect.
Solution 2:
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.