Wie kann ich aus einer Liste Duplikate entfernen, ohne die Reihenfolge zu ändern? Meine Liste ist einige 100.000 Einträge lang, also sollte der Algorithmus nicht zu langsam sein.

Die Erweiterungsmethode Enumerable.Distinct kannst Du auf eine beliebige Collection, die IEnumerable implementiert, anwenden. Sie liefert Dir genau das zurück: Die Collection in der gleichen Reihenfolge wie ursprünglich, aber ohne Duplikate.

"More Effective C#" behandelt diese Frage als Beispiel für den Einsatz von yield. In etwas so:

public static IEnumerable<T> Unique (IEnumerable<T> inp) {
    var valset = new HashSet<T>;
    foreach (T t in inp) {
        if (valset.Add (t)) {
            yield return t;
        }
    }
}

<snip> ohne die Reihenfolge zu ändern?

Das ist der Kackpunkt. Damit ist ein Algorithmus mit einer Vorsortierung ausgeschlossen.
Ein wichtiger Punkt währe zu wissen: sind in der Liste wirklich nur Doubletten, also max. Vorkommen eines Elements == 2, oder kann ein Element auch 3 und 4mal enthalten sein?
Das währe die ungünstigste Voraussetzung, denn dann wird das Entfernen ein O(Log n)-Vorgang.

<snip> also sollte der Algorithmus nicht zu langsam sein.

Je genauer du deine Liste beschreibst umso leichter kann man dir einen Vorschlag unterbreiten.

Servus,
Klaus

So wie ich das sehe muss hier auf jeden Fall sortiert werden.
Was du aber probieren kannst ist folgendes:
Pack die Werte erstmal in ein 2-dimensionales Array. In Dimension 1 kommen deine Werte rein. In Dimension 2 nummerierst Du diese Werte durch (von 1 bis n) anschliessend sortierst Du die erste Dimension (und nimmst dabei natürlich die zweite entsprechend mit). Nun folgt ein einfacher Gruppenwechsel wobei du doppelte Einträge entfernst. Im letzten Schritt sortierst Du nach der zweiten Dimension und hast nun in der ersten jeden Wert nur einmal in der ursprünglichen Reihenfolge.