I used to open my pdf with xpdf on Debian / Ubuntu, wishing I had Preview.app running like on Mac OS X. Finally found an Gnome application which is damn fast : evince. Features are fast tumbnails creation, online text search and a simple graphical interface.