Gaming on cell phones is not that bad! I love it.
However, it is (currently) only suited to certain types of game, and you need to recognise that before you waste loads of money trying duff ones like I have. Yes, the no diagonal thing is a bit pants (though some games get round it by using the '1' and '3' keys). I think the biggest flaw with current phones (well, at least on my Motorola E398) is actually not being able to press one button at a time. AHH!!
Rainbow Six 3 is a great demonstration of what you can do on a phone, and do it right. Almost a perfect mobile phone game. Another great game is Ancient Empires, perfectly suited to mobiles. Might and Magic is also a good example, shame the difficulty curve is completely stupid on that one though.
A really nice game, but let down by not being able to press one button at a time is Colin McRae 04 (Super Cars II plan view, NOT the crappy 05 version). I can just about make the second level, but not being able to brake while turning makes it impossible on that dirt... (at least for me).
Other good games suited to mobiles are:
I have played some more, but I will have to remember what they are. I'll add them here when I think of them.