I would think pagination would give you faster initial response, though of course the time to view the entire dataset would take longer. The actual query response time probably wouldn't be much different, but then there would be less data to transmit between MySQL and PHP, less data for PHP to process in fewer loops, and then less data to transmit across the network to the browser.
As with any performance questions, if you can do some metering and determine where the specific bottlenecks are, then you don't have to speculate and optimize by trial and error, but can instead concentrate on those specific bottleneck points.
Also, when you say you've optimized your database tables, did that include creating indexes for columns which are used in your "where" clauses?