Good build, but I think that's overkill for the needs expressed in the first post. I'd go to NewEgg and look for an all Gigabyte build + an ATX InWin case w/ preinstalled 350W power. InWin's factory installed 350Ws are more than enough for basic builds w/ one video card and up to two hard drives. Buy a decent toolless case w/ PS included and you'll save $100.
$59.99 IN WIN IW-C589T.AQ350BL Black Steel ATX Mid Tower Computer Case 350W Power Supply - Retail
Newegg.com - IN WIN IW-C589T.AQ350BL Black Steel ATX Mid Tower Computer Case 350W Power Supply - Retail
$89.99 GIGABYTE GA-P35-DS3L LGA 775 Intel P35 ATX All Solid Capacitor Intel Motherboard - Retail
Newegg.com - GIGABYTE GA-P35-DS3L LGA 775 Intel P35 ATX All Solid Capacitor Intel Motherboard - Retail
$209.99 Intel Core 2 Duo E8400 Wolfdale 3.0GHz 6MB L2 Cache LGA 775 65W Dual-Core Processor - Retail
Newegg.com - Intel Core 2 Duo E8400 Wolfdale 3.0GHz 6MB L2 Cache LGA 775 65W Dual-Core Processor - Retail
$84.00 CORSAIR XMS2 2GB (2 x 1GB) 240-Pin DDR2 SDRAM DDR2 1066 (PC2 8500) Dual Channel Kit Desktop Memory - Retail
Newegg.com - CORSAIR XMS2 2GB (2 x 1GB) 240-Pin DDR2 SDRAM DDR2 1066 (PC2 8500) Dual Channel Kit Desktop Memory - Retail
That covers the barebones for under $500. I haven't played PC games for awhile so I can't comment on the sys req. for AoE III, but I doubt you'll need to drop more than $75 on a video card. IMHO it pays to be a year behind the curves, so I'd probably look at an 8600GT or ATI equiv. Heck, an 8400 is only $40, so the whole build is still $500.
Go micro ATX and shave another $100. Plenty of options.
If you're hesitant to muck around inside your own PC, you could also take a shopping list like the ones posted here to a specialty computer center, one of the custom/boutique type places where the geeks build computers from the ground up, and tell them, "I'm thinking of buying this, this & this through NewEgg and building a PC ..." Odds are you can get one of these stores to build it for you for less, just to get your business.
Remember, if you can get the parts for these prices through NewEgg, the stores are getting them for less. Shop around.