Hallo!
Ich möchte mich da einem meiner Vorredner anschließen. Ein bisschen präziser könnte die Fragestellung schon sein, denn ansonsten bleibt der Begriff der Schwierigkeit oder Komplexität doch eher schwammig.
Wenn du komplizierte Steuerung meinst, dann wurdest du ja schon auf das Genre der Simulationen hingewiesen. Die alten (Kampf-)Flugsimulatoren sind da ja nur ein kleiner Teil, es gab auch U-Boot-, Schlachtschiff-, Weltraum-, Panzersimulationen etc. Alle mehr oder weniger komplex.
Auch auf dem Sektor der Prügelspiele gibts ein paar, die einen fast zur Verzweiflung bringen. Das wär dann zwar eher was fürs Konsolenbrett, außerdem bin ich da nicht ganz so bewandert. Spontan fiele mir da Killer Instinct für den SNES ein. Hektischen Knopferldrücken bringt dich da keinen Schritt weit.
Die nächste Kategorie wären dann Wirtschaftssimulationen und dergleichen. Da ist zwar die Steuerung (vorzugsweise) relativ simpel, dafür kann der Rest recht knackig sein. Dazu zähle ich jetzt der Einfachheit halber auch die Sim City Reihe. Wenn du da nicht auf Micromanagement stehst, hast du beinahe schon verloren 
Anderes Kapitel: Strategiespiele. Obwohl viele davon nicht wirrklich vom Stein-Papier-Schere-Prinzip abweichen, gibts da so einige dies wirklich in sich haben (nein, C&C meine ich damit nicht). Spontan fallen mir Earth 2150 und 2160 ein, sowie der absolute Klassiker Total Annihilation und sein inoffizieller Nachfolger Supreme Commander. Alle 4 waren mir dann doch zu hart, obwohl ich das Spielprinzip liebe 
Wieder was anderes: Spiele die dich mit der schieren Auswahl an Möglichkeiten fast erschlagen. In diese Kategorie fallen einige exzellente Rollenspiele, wie zum Beispiel die Elder Scrolls Reihe (vor allem Morrowind) oder die Gothic Reihe.
Und nicht zu vergessen: Adventures. Je nach Spiel reicht die Qualität der Rätsel von leicht bis anspruchsvoll, und von einfallslos bis absolut durchgeknallt. Teilweise sogar so schlimm, dass man ohne Hilfe NIE auf die richtige Lösung kommen würde (Day of the Tentacle z.B., oder auch Discworld). In der eher ernsthafteren Sparte fand ich die Myst Reihe sehr gut. Und mir jedenfalls hat der Schwierigkeitsgrad absolut ausgereicht.
Das war jetzt nur mal das was mir spontan zu dem Thema eingefallen ist. Du siehst, die Bandbreite ist nicht gerade die kleinst. Also wenn du da mal etwas deutlicher werden könntest, dann können dir bestimmt auch mehr Leute helfen.
Grüße
Steve