For a desktop:
Just get an i5 or i7 with a compatible motherboard, a HD7970 or GTX680 or equivalent, 8-12GB RAM and an SSD, can't go wrong with that. Make sure the motherboard you picked actually supports dedicated graphics cards. Do not cheap out on the PSU. Cheap out on the DVD/Blu-ray drive instead. Make sure your PSU is large enough (be conservative, but not overly conservative, ask on forums and use the reported power usage - at load - of your components to find out what you would realistically need) Include your favorite speakers and headphones. If you need a monitor, pick your favorite, just make supports it supports at least DVI (they are all the same nowadays though, so get the biggest one you can afford or something). Make sure you don't get "passive cooling" components, that's for office desktops, not gaming rigs. Traditional air cooling will work fine unless you are into overclocking or are playing in a sauna.
Last but not least, check reviews from many websites before making a decision. Use common sense. Finally, take good care of your computer. Please.
My three year-old HD6950 still plays most games (even recent ones) at maximum settings at full framerate. It is difficult for a brand new computer to "lag" unless you make really poor choices for your components (that, or your computer is oozing with malware, but that is a different issue).
Refurbished desktops can be a good alternative too, as Prinz Eugn said, but you usually have to do some hunting around to make them worth your while. Again, make sure you're getting a good deal, it's better to check reviews before than feeling sorry after.
A desktop is generally a better investment than a laptop if you are usually in the same place when gaming. If that is not the case, get a laptop, or you will have to deal with the lack of mobility to the bitter end and will regret your purchase. That said the price tag on desktops can be a bit high when you're just starting out as you need to buy all the extra stuff established gamers already have, such as monitors and power supplies, the real price savings are during upgrades where you only need to swap in a few components at a time.
For a laptop:
I don't know, really. Sorry. But laptops are a good choice if you're in different locations for extended periods of time. Make sure your laptop is small enough to be carried, though. 19" monstrosities are not actually laptops, because they are too heavy to carry around. 17" is at the edge, and 13" is too small for some people. 15" is about the right size, IMHO. If possible you should try out laptops before acquiring them to check their usability/ergonomy, that doesn't apply to desktops obviously (keyboards are separate).