Good luck getting a laptop that will run any of those games well* for less than $600. Buying it in-store would need to be a mighty fine deal for it to be worth it.
You can probably get a refurbished laptop from Newegg or Amazon. The retail price of these is often around the $1000 mark but gets sold for $400-600 because the packaging was messed up or someone bought it and didn't like it. It's "used" in most circumstances, but approved for resale.
I'd say brand matters, but I'm a bit uneducated and biased. I hate Lenovo and HP laptops, but they both might be pretty great if you get a certain model.
Edit:
*: My laptop cost me $700 and it can run CK2 if everything is disabled (literally everything, no rivers, no water, no trees, no cities, low resolution, etc) with lag (unplayable with the new DLC), it can run Civ V on the lowest settings and low resolution semi-okay on sizes below Standard, and it can barely run Rome: Total War, let alone Empire, Napoleon, Shogun 2, Rome 2, etc.