バックグラウンドには回せない。キャッシュも使えない。しかし遅い。

　処理によっては、バックグラウンドにも回せませんし、キャッシュも使えない（効果が低い）、だというのに遅い、というものがあります。
　WEB APIを多用した処理が代表例です。
　これは基本的に外部の問題なので、こちら側で対応するのも限界があります。

　みんなの動画サーチで言うと検索画面がこれにあたります。youtube,youku,dailymotion,tudouと４つもWEB APIもしくは外部のRSSを取得しなければならないため、これらすべての応答速度を合計すると悲惨な数字がでます（よくて数秒、下手をすると３０秒を超えてタイムアウトします。とくにtudouが遅い！）。　

AJAXを使って見かけの応答速度を速める

　こういう場合はAJAXを使って表示を小出しにするようにして、見かけの応答速度を速めることでユーザーのストレスを軽減することができます。すべての情報が表示されるまでの時間は遅くなりますが、それでも画面の遷移待ちの状態で何秒も経ってしまうよりははるかにましです。

　なお、AJAX利用をする際、一からコーディングしていると大変なので既存のフレームワークを使うと良いです。ちなみにみんなの動画サーチではprototypeを使っています。

　下はPHPではなくJAVASCRIPTの例です。

function showHTML(address,id_name){
	new Ajax.Request(address, {
		method: "get",
		onSuccess:function(httpObj){
			$(id_name).innerHTML = httpObj.responseText;
		},
		onFailure:function(httpObj){
			$(id_name).innerHTML = "エラーで読み込めませんでした";
		}
	});

}

AJAXのデメリット

　AJAXで表示を分けたとしても、分けたあとの表示が遅いようだと結局ユーザーはストレスに感じますから過信は禁物です。

　また、AJAXを利用すると、テキストの量が減る、画面数が減る、といった理由によりSEO上不利になってしまいがちなので要注意です。
　みんなの動画サーチでは、検索画面ので利用している４つのWEB API（かRSS)の中でもyoutubeだけは応答速度に目をつぶってAJAXなしで処理していますが、それはこのSEO上の不利を嫌ったためです。

処理そのものを変える手もある

　外部データの取得をそのつど行うことは止め、あらかじめ一気に取得しておいて自前で保存するようにするなど、処理そのものを変更する手もあります。
　FOOOOOがおそらくそうだと思います。
　場合によってはそういう力技も考慮にいれるといいでしょう。