Company of Heroes (rts) y COD 4: Modern Warfare (fps) son los que más me han gustado.
FPS hay un montón: Bioshock, Gears of Wars, Crysis, CoD 5, Dead Space si quieres algo rollo survival horror... tirando más al rol Fallout 3 y Mass Effect. Hay muchos más que me dejo.
En cuanto a estrategia, los que más he jugado aparte del Company han sido el Dawn of War I y II y ESDLA: Batalla por la tierra media II, también puedes mirate el Command & Conquer 3 y el Red Alert nuevo. De estrategia por turnos están el Medieval: Total War y el Empire: Total War, que pertenecen a la misma saga, y el Hearts of Iron, ambientado en la segunda guerra mundial (bastante complejo éste último). De simuladores, los Anno están muy bien, de los pocos que se salvan del género últimamente para mi gusto.
Con esto ya tienes para empezar xD