Ver 1.8.6やマニュアル↓に載っている安定ソートの方法を使うなら、こんな感じかな。

instance method Enumerable#sort_by
http://doc.ruby-lang.org/ja/1.9.2/method/Enumerable/i/sort_by.html

i = 0
fruits.reverse.sort_by {|v| [v[0], i += 1] }.reverse