Most laptop overheating issues are caused by household dust building up inside the cooling fan / heatsink. Sometimes this can be removed with compressed air but usually you have to take the laptop in for repair to have it cleaned fully.
I repaired laptops for a large retail company and this was the most common issue - the longer the laptop is used for the worse it gets. Smoking makes the problem 10 times worse as the nicotene causes the dust to stick to it and clog up the air flow through the heatsink. A laptop should not overheat when playing a game it can handle - it's probably a clogged fan. Some laptops have a panel that can be removed underneath to gain access some the motherboard has to be removed. Most high end gaming laptops have the CPU / GPU easily accessible for upgrades and cleaning.
Might be worth seeing if it just needs a clean. If anyone isn't technically minded most local repair shops should clean it out for a small fee. On the other hand it could be a good excuse to buy a new laptop.
I wouldn't be able to recommend any particular brand but as someone already suggested go for at least an I7 and as for the GPU either is fine. The AMD's seem to run cooler than the Nvidia cards.
