Как вывести на страницу 5000 строк безболезненно?
Единственное решение в данному случае это показывать на экране ограниченный список элементов, постепенно добавляя/убирая те которые видно/не видно. Придется программировать на js или искать готовое. Со стороны пхп передавать только голые данные без html оберток и тд.
Очень просто. 
Надо всего лишь уменьшить количество рюшечек, бантиков и колокольчиков. Отказавшись от всех этих яваскриптиков, сортировочек, онлайн редактирований и прочего. 
Также надо отказаться от таблиц и формировать страницу из независимых блоков.