Evince performance (Hint: slow)
Solution 1:
There is no solution for Evince yet (2016). But you can use Okular (free software, available in your package manager), and change the settings of the viewer to greedy (Settings -> Configure Okular -> Performance -> Greedy) which will load all pages. You can then skip forward and back as fast as you want, the pages are displayed at once!
Solution 2:
I think it is a bug: https://bugzilla.gnome.org/show_bug.cgi?id=645796 - Evince has performance problems with large/complicated pdfs.