Скорость появления страницы в первую очередь зависит от ее объема в килобайтах. Поэтому на странице 404 нежелательно размещать рекламу, длинные тексты или графику (кроме логотипа).
Кроме того, нельзя допускать, чтобы несуществующую страницу путали с обычной. Поэтому на странице с ошибкой не должно быть основного меню сайта, верстки и цветов типовой страницы.