コンピュータサイエンスの授業をします。

１ピタゴラス数を重複さずに順番に見つける。
２素数を重複さずに順番に見つける。
３ＸＹ平面上の点を3点ずつ（線が交差する事なく）結ぶ。---できる図は1通りではありませんが、1つだけできたら終わりにする。---計算量は大体点数の４乗になります比例します。

ソート以外だと、エイトクイーンが定番ですね。
条件の[4]までは満たしていると思います。


8クイーンのどのあたりが教材として優れているかといえば、
チェスの盤面がイメージしやすいため、
何をしようとしているか想像しやすいところにあります。

逆に高度なアルゴリズムでは、初見の生徒が
何をしているかパッと想像できないと思います。

また、一桁クイーンなら短時間で計算できるとか、
単純な解法ならコードが難解にはならないとか、
ゲームへの応用を想像できる（から面白い）、
などというのもメリットです。

それから、ご質問の意図とは異なってしまいますが、
ソートが実際にどのように使われているのか、
説明する方向でも面白くできるかもしれません。
（プログラミング自体に興味がなくても面白いと思えるかも）

たとえば、ブログのエントリが
日付順に並んでいるのもソート（の結果）ですし、
RPGの道具屋でアイテムが
価格順に並んでいるのもソートでしょう。

生徒側の心理を見たときに、
それが実用的にどのように使われているか分からないと、
自分の役に立つと思えず、興味も湧かないのだと思います。

普通の数学との関係からすると、変数の多い連立一次方程式の解法はどうでしょうか。

詳しいことは私も分かりませんが、いわゆるクラメルの公式は計算量が多くて使い物になりません。

巡回セールスマン問題、と思ったが、最適解を求めるのが大変だから、出てきた解を評価できないなぁ。

最近だとこんな記事がありましたね。

Atomの重要なプリミティブの最適化 | コンピュータサイエンス | POSTD
http://postd.cc/optimizing-an-important-atom-primitive/

Atomというエディタで、テキスト内部の範囲を表現する「マーカ」という構造体の扱いによって処理速度が大きく変わってくるという内容です。

単にテキスト内部の位置を保持するだけのマーカの処理でも、数が多くなると計算量が問題になってくるわけです。
最近流行りのいわゆるビッグデータやディープラーニングなども大概データ量が多いので、常に計算量を意識しないと、まずまともに動きません。
なので計算量のオーダーの話が古い、なんてことはありませんよ。

さて上記のマーカの問題に戻りますが、「効率的な探索方法」のところで、探索木の中で22番目の位置を含む領域にアクセスするのがO(log(n))とされています。同じように22番めの要素にアクセスする場合でも、配列に格納して22番目に直接アクセスできればO(1)、配列ではなく隣接リストでデータを持っていて最初から一つずつたどる必要があればO(n)になります。
他にも例えば「全てのマーカの対を考え、そのマーカに重複する部分があれば出力しろ」といった問題をナイーブに処理するとO(n^2)になるでしょう。

上記の話は「一つの問題」ではないので、お望みの回答ではないかもしれません。
ただ個人的には、何に使うのかわからない呪術的なアルゴリズムを幾つか読み解くよりも、普段自分が書いている簡単なプログラムの計算量を確認したり、データを1億倍にした場合の悪夢を体験させたりした方が良い学びになるかと思います。

計算量を「特殊なアルゴリズムを利用する際に優劣を決めるためのもの」と考えるとつまらないですが、「プログラムが遅くて困ったときに見直すと、100倍以上の改善の可能性があるもの」と考えると面白いですよ。