One of my roommates wants to get a PC game for my other roommate for Christmas -- he can't really do fast-paced stuff without feeling rather ill, so FPS / etc is out. He's playing Civ 4 now - already let him take Supreme Commander and Medieval 2: Total War, so those are out.

I'm thinking AoE 3, Dawn of Discovery..? Any ideas? He has a Core i5 750 / 4Gb / 4670.

C&C3 and its expansion

Hell of a PC, Almost the same specs as mine (Although it's bricked atm)
Hearts of Iron 3, although you need extreme patience because it's buggy as all hell and will be for a while. Great game though.
The classics like Starcraft are always good, Empire at War is one of my personal favorites (although I can understand people who hate it). Rebellion is pretty deep. Sins of a Solar Empire is a great game.

I can sink hours into one map of Empire Earth 2 without even realising it. I've heard 1 and 3 aren't so great, though.

Rebellion? As in SW: Rebellion? I thought that didn't fare too well. The game's menu's pretty cool, but the space battles really shouldn't have been in that game.

"Dating" is the most difficult yet rewarding strategy game ever. I would recommend that to both you and him.

A bit different, but Black and White 1 and 2 are very fun

Galactic Battlegrounds. *creates horde of wookie berserkers and unleashes them on your camp* Sigh.. I love those guys.

Aw, I thought this was going to be a recommendation for an old-school awesome strategy game. I'll just derail for a second, get DosBox and run Master of Magic, it rules.

Rise of Nations (plus the expansion) is my favorite RTS. Imagine AoE, but requiring a bit more tactical thought for battles, some form of diplomacy, and some influence by turn-based strategy games. For instance, enemies are weaker at their sides and especially their backs, and battles can be swung by superior positioning and movements. It covers all of human history, has loads of options, looks pretty good, and runs great on older computers.

You must be a dating fanboy. That stuff is so overrated, and its sequel is even worse. They take all the good parts out, and leave the stuff you hate.

On a serious note, Age of Mythology.

HELL YEAH, GOLDEN COLLOSI, VALKYRIES, AND ALLIGATORS THAT SHOOT FRIKKIN' LASERS.

Oh yeah, and Homeworld is a must.

It's a love it or hate it game.
The graphics are *** terrible (even for when it was released) and it can be unintuitive and clunky at times.
I have only ever played it once, in an epic 5 hour session as the Rebellion.
Taking Coruscaunt felt so sweeeeet.

Age of Empires II (Age of Kings) and it's expansion The Conquerors

1 wasn't bad, 3 was just absolutely terrible. Worst rts ever

3 is like if the developers decided the remove everything that made 2 good, and then focus on the few bad things.