Here is my take.
FPS, get STALKER (3rd most creepy game i've played, right after AvP 1/2 play as the marine). I'll let others rant on about COD4/Crysis, but i will say that COD4 will bore the hell out of you if your getting tired of FPS's.
Supreme Commander is great with the MASSIVE maps with hundreds/thousands of units in play, 3D graphics (press the space bar to swivel the camera when zoomed in) and... well epic battles. You control armies rather then small groups of units. But i would get something else because it can burn you out if you play it a lot, campaign and skirmish maps can take a while to do (1+ hours). Also note that it's a system hog.
I've been meaning to try Warhammer RTS's, but only tried the winter assault demo. Might be good to get a game bundle for this. I tried Command & Conquer 3 but quickly lost interest.
You could also try Homeworld 2, it's a bit old by now but it's a very refreshing RTS.
World in Conflict is the BF2 of RTS's, very easy to get into online play without getting your ass handed to you a great deal. Single player is only a advanced tutorial for multiplayer though. Also 3D and can be very fun to just spectate and warch the carnage online.
Company of Heros rocks as well. It's tempting to say it's better then supreme commander, but the 2 games are completely different.
Then Black and White 2, where you play as a god guiding your people. Best decribed as similar to the Total war series, but city vs city and you build up your city like in sim city.
Then there is the Total war series, like Civilization but with RTS battles.
Mechwarrior 4: Mercenaries (stand alone, superior the MW4) is also a very good game, a little old by now though, nothing quite beats stomping around the mech of your choice with the weapons and squad members of your choice. One of the very few games i've ever replayed 3 times. If you really want old school there is Mech commander RTS style movement but you have what you started each mission with.
Then there are RPG's, i'm currently going through Neverwinter Nights 2 and am enjoying it. If you do get it, you should also install the expansion "Mask fo the betrayer" as it adds new content and fixes problems that will also transfer to the original NW2.
THEN there are the MMO's. Main ones now are Wow, Guild wars, EvE, Pirates of the Burning Sea, Lord of the Rings Online, EverQuest 2, Final Fantasy XI, City of Heroes/City of Villains , Tabula Rasa, Dungeons & Dragons Online , RuneScape. I can't give any useful advice other then look into how each game plays yourself. I've stopped playing MMO's because i can't stand grinding, but Age of Conan/Darkfall (if DF is not vaporware) i will try in hopes of a fun game this time around.