クイックソートのpivotの決め方について

まず、中央値や最大値を選ぶ方法とランダムに選ぶ方法では、決定的なアルゴリズムになるか確率的なアルゴリズムになるかという大きな違いがあります。クイックソートはピボットの選び方を間違えると停止しないアルゴリズムです。このためピボットをランダムに選んでしまうとソートが停止しない可能性も残ります。またそれ以外にも、最近の計算機において「ランダムな値を選ぶ」というのは中央値や最大値を選ぶのに比べるとコストが高い計算であることにも注意が必要です。

たとえば日本語版 Wikipedia に載っているクイックソートのアルゴリズムにおいては、配列の要素たちの唯一の最小値を毎回ピボットに選んでしまうと停止しません。「先頭ふたつの最大値をピボットにする方法」や「3 つ選んでその中央値をピボットにする方法」はソートを停止させる保証を得るために必要な手間です。

更に、クイックソートではなるべく配列の要素たちの中央値をピボットに選べると要素間で比較する回数の平均値を減らせます。配列から 3 要素選んで（たとえば先頭の 3 つを選んで）その中央値をピボットとするやり方は、これを期待しています。実際平均的には「先頭ふたつの最大値」方式より高速になる……はずです。

最後に再帰的に中央値を求めるやり方についてです。たとえば次のような実装を考えてみましょう：全体を三分割し、それぞれについて「3 つ要素を選んで中央値をとる」操作をした結果を m1, m2, m3 とし、更にこれら 3 つの中央値となる要素をピボットとする。これに似たやり方が C 言語の qsort 関数の実装を追った論文 "Engineering a Sort Function" (Bentley & Mcilroy. 1993. リンク) で検討されており、当時の実験では単に「3 つ選んで中央値をとる」方法よりも時間計算量が小さい、と主張しています。

個人的にはこのあたりの優劣は実際に実装して計測してみるのが一番だと思っています。このあたりをチューニングし始めると、そもそも中央値の近似計算にどの程度実時間がかかるのか、や、配列の要素の入れ替えだとかいった処理にどの程度実時間がかかるのか、などといった要素が絡んでくるため、どのような実装が速いのかを決める概算が簡単にはやりづらくなります。たとえば最近の CPU はかなりうまく分岐予測をするので……とか、配列が無茶苦茶長いとキャッシュに乗るかどうかが問題になってくるので……、とかいった事情が無視できなくなってきます。このため最終的には実験をして速度を確かめるのがてっとりばやいです。

以上をまとめると：一般論としては「先頭ふたつの最大値」や「ランダム」よりも「（何かしらの規則にしたがって選ばれた）3 つの要素の中央値」が平均的には速くなりそうですが、実際のところは実装や計算機によるので、最終的には実験してみてください。

補足：たとえば英語版 Wikipedia の Quicksort のページにも pivot selection について幾らか書かれているので参考になると思います。ソートの高速化という意味で関連する、イントロソートや dual-pivot quicksort についても触れられています。

ピボットの選択が偏る可能性を考えるなら、どういう入力が与えられるかも考えなければいけません。
どれも同様にピボットが偏る入力が存在するのでそういう意味では一長一短ですが、実際にどういうデータが与えられやすいかを考えれば2のようにソート済みのデータが入力されるとピボットが偏るようなやり方は最悪です。1,3,4は具体的な操作が分からないので一概には言えませんが、おおむね3よりも4、4よりも1のやり方のほうがピボットの選択が規則的になるので避けたほうがいいです。
最終的に個人的な優先順位は3 > (4 > 1) > 2でしょう。4と1は具体的な操作が不明なのでカッコつきです。