You could try something like the Nokia 6630/6680 or the Sony Erricson S700i, both are very powerful devices as phones go. The Erricson has better features and the operating system is very sturdy. It has cool features as an organiser aswell. Its very cool for games because it has such a big resolution on it.
Although the nokia series 60 phones (such as 6630/6680) in my opinion aren’t as useful as the Sony Erricsonon, Games are more available for them since they are for now more common. So if you want a phone specifically for playing games A Nokia would probably be best as you get New releases for them quicker.